[알고리즘] 문자열 KMP, Rabin Karp

문제 정의

• A라는 문자열 안에, B 문자열이 어디에 몇번 속해있는지 확인

문제 접근 - KMP

• B 문자열의 fail 배열를 먼저 구함
  • fail 배열 : 각각의 문자가 몇번 반복되었는지 확인
• A 문자열과 fail 배열을 비교
• KMP 개념이 다소 복잡해서, 잘 설명해주신 바킹독님 블로그를 참조하시면 좋을것 같습니다.
• https://blog.encrypted.gg/857?category=773649

문제 접근 - Rabin-Karp

• 문자열의 각각의 글자를 해시값으로 변환
• 문자열의 각 위치에서 한글자씩 빼고, 더해주면서 해시값을 비교
  • 해시값 구할때 a = 302, p = 1e9+7 사용

시간복잡도

• M : A 문자열의 길이
• N : B 문자열의 길이
• O(M+N)

대표예제 : 백준 1786 찾기

• KMP

#include <iostream>
#include <string>
#include <vector>
 
using namespace std;
 
vector<int> fail(string& s) {
    vector<int> f(s.size());
    int j=0;
    for(int i=1; i<s.size(); i++) {
        while(j>0 && s[j] != s[i]) j = f[j-1];
        if(s[i] == s[j]) f[i] = ++j;
    }
    return f;
}
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    vector<int> f = fail(P);
    
    int j=0;
    vector<int> rs;
    for(int i=0; i<T.size(); i++) {
        while(j>0 && T[i] != P[j]) j = f[j-1];
        if(T[i] == P[j]) j++;
        if(j==P.size()) {
            rs.push_back(i+2-P.size());
            j = f[j-1];
        }
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    return 0;
}
 
 

• Rabin-Karp

#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
typedef long long ll;
 
ll a = 302;
ll p = 1e9+7;
ll powa[1000010];
 
int main() {
    string T,P; getline(cin, T); getline(cin, P);
    
    int lenT = T.size();
    int lenP = P.size();
    if(lenT < lenP) {
        cout << 0 << '\n';
        return 0;
    }
    
    
    // a의 제곱값을 미리 구해놓음
    powa[0] = 1;
    for(int i=1; i<P.size(); i++) {
        powa[i] = powa[i-1] * a %p;
    }
    
    // 각각 P길이만큼 해시값 구함
    ll hashT = 0;
    ll hashP = 0;
    
    for(int i=0; i<P.size(); i++) {
        hashT = (hashT + T[i] * powa[P.size()-1-i]) %p;
        hashP = (hashP + P[i] * powa[P.size()-1-i]) %p;
    }
    
    vector<int> rs;
    if(hashT == hashP) rs.push_back(1);
    
    for(int i=1; i<=(T.size()-P.size()); i++) {
        // 앞글자 빼고, a만큼 곱해서 한자리씩 올리고, 새로 한글자 추가
        hashT = (hashT - T[i-1] * powa[P.size()-1])%p;
        // 음수인경우 확인
        if(hashT < 0) hashT += p;
        hashT = hashT * a % p;
        hashT = (hashT + T[i+P.size()-1] ) % p;
        if(hashT == hashP) rs.push_back(i+1);
        
    }
    
    cout << rs.size() << '\n';
    for(int x : rs) cout << x << '\n';
    
    return 0;
}