[Algorithms] KMP 알고리즘

KMP.. 아픈 기억이 있는 알고리즘. 아무튼 그동안 이러저러한 이유로 KMP 공부를 미루고 있다가 최근에야 다시 제대로 배웠다. 아이디어 자체는 간단하다. 문자열 $S$에 패턴 $P$를 매칭할 때, $P$의 $i$번째까지의 문자열에 대해 접두사이면서 접미사인 문자열의 최대 길이(여기서 접두사와 접미사는 원래 문자열을 제외하고 말한다.)를 실패 함수라고 정의한 후 이를 잘 이용하면 $O(|S|+|P|)$에 패턴이 존재하는지 찾을 수 있다.

 

$S$의 중간 부분부터 $i-1$번째까지 문자열과 $P$의 $p$번째까지 문자열이 일치한다고 하자. $S$의 $i$번째 문자를 새로 매칭시키려고 할 때, 만약 성공한다면 $p$를 1 증가시키면 그만이지만 실패할 경우, Naive하게 할 때는 매칭을 시작한 곳 다음 부분부터 다시 $P$의 처음 부분과 매칭을 시작한다. 하지만 여기서 $S$의 $i-1$번째까지 매칭 가능한 $P$의 위치들을 순서대로 훑어볼 수 있다면, 불필요한 매칭들을 건너뛸 수 있게 된다. 이 때 $S$에서 매칭시키는 인덱스를 감소시킬 필요가 없어지고 따라서 매칭을 빠르게 할 수 있는 것이다.

 

중간부분부터 $i-1$번째까지의 문자열과 매칭되는 최대 $P$ 접두사 길이가 $p$임을 알고 있는 상태에서 $i$번째 문자까지 매칭이 가능한 최대 $P$의 접두사 길이는 어떻게 구할까? $i-1$번째까지 매칭가능한 $P$의 접두사에 대해, $S$에서의 매칭이 시작되는 부분을 오른쪽으로 당긴다고 할 때 일정 길이의 접두사와 접미사가 같아야 함은 쉽게 알 수 있다. 예를 들어 $S=\cdots abcabc \cdots$에서 $P=abcabd$를 찾는다고 하자. 여기서 $abcab$까지 매칭을 시켰는데, 그 다음 문자인 $c$와 $d$가 다르므로 $S$에서의 매칭 시작 지점을 오른쪽으로 당기려고 한다. $abcab$를 적당히 밀어 $S$의 어떤 지점부터 $i-1$번째까지 $ab$가 매칭되게 바꾸는 것만이 가능하다. 이런 식으로 $i-1$번째 문자를 매칭시킬 수 있는 위치들 중 그 다음 위치가 $S$의 $i$번째 문자와 같을 때까지 $p$를 감소시킨 후 $i$번째 문자를 매칭시킨다. 위 예시에서는 한 번만 밀어도 그 다음 문자가 $c$로 동일하여 매칭을 이어나갈 수 있게 된다. 하지만 $acabacac \cdots$에 $acabacae$를 매칭시킬 때를 생각해보면 $acabaca$까지 매칭 후 매칭이 실패하여 $aca$, $a$ 순으로 매칭으로 두 번 옮겨야 한다. 이처럼 여러번 실패함수를 이용해 매칭시킬 $P$의 위치를 바꾸다가 새로운 문자가 매칭 가능하거나 매칭이 아예 실패할 때까지 $P$를 오른쪽으로 밀면서 매칭을 이어나가는 것이 KMP 알고리즘이다. 실패 함수는 접두사와 접미사가 같은 최대 길이를 의미하므로 가능한 매칭을 건너뛰는 경우는 발생하지 않는 것 또한 알 수 있다.

 

실패함수는 자기 자신과 매칭시킨다고 생각하며 구하면 된다. $i-1$번째까지의 실패함수가 구해져 있다면 다음 실패함수를 구하는 것은 자기 자신과 매칭시키는 것과 동일함을 알 수 있다. (DP라고 볼 수도 있겠다.) 실패함수를 구하는 과정에서 $p$를 증가시켰다가 감소시켰다가 하는데, 최대 $O(|P|)$번 증가하고 감소할 수 있음을 알 수 있다. 실패함수를 만들 때나 패턴을 매칭시킬 때나 $i$번째 문자가 매칭 가능할 때만 $p$가 1씩 증가하므로 최대 $O(|P|)$만 증가함은 자명하고, while문을 돌면 반드시 $p$값이 감소하는 것 또한 자명하다. 매칭을 시킬 때도 비슷한 이유로 $O(|P|+|S|)$만큼 $p$값이 변화한다.

 

https://www.acmicpc.net/problem/16916

위 문제는 기본 KMP 구현 문제로, 그냥 하면 된다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define reset(x) memset(x, 0, sizeof(x))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 101010;
const int INF = 1e9;
const ll LINF = 1e18;

vector <int> get_fail(string t) {
	int p = 0, n = t.size();
    vector <int> F(n);
	for(int i = 1; i < n; i++) {
        while(p > 0 && t[i] != t[p]) p = F[p-1];
        if(t[i] == t[p]) p++;
        F[i] = p;
	}
    return F;
}

bool KMP(string s, string t) {
    int p = 0, n = s.size();
    vector <int> F = get_fail(t);
    for(int i = 0; i < n; i++) {
        while(p > 0 && s[i] != t[p]) p = F[p-1];
        if(s[i] == t[p]) p++;
        if(p == t.size()) return true;
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    string s, t;
    cin >> s >> t;
    cout << KMP(s, t);
}

 

https://www.acmicpc.net/problem/2401

이제 이를 응용한 dp문제를 풀어보자. 어떤 길이 $k$의 짧은 문자열이 긴 문자열 $s$의 $i-k+1\textrm{~} i$에 매칭된다고 하자. $dp_i$를 $s$의 $i$번째 문자까지 매칭시켜 얻을 수 있는 최대 매칭 문자 수라고 정의하면, $\displaystyle dp_i=\max(dp_{i-1}, \max_k (dp_{i-k}+k))$임은 간단히 알 수 있다. KMP 알고리즘을 $p$가 $k$일 때 멈추지 말고 위치를 기록한 후 다시 실패함수를 이용하여 돌아가는 일을 반복한다면 모든 매칭을 발견할 수 있고, 적당히 해당 문자열의 길이를 해당 자리에 기록한다면 문제를 풀 수 있다.

 

하지만 짧은 문자열의 개수 $N \leq 500$이고 $L \leq 10^5$이기 때문에, 대략 최악의 경우 $5 \times 10^{7}$의 정수형 변수를 기억해야 할 수도 있다. 따라서 메모리 초과가 나게 된다.

 

이를 막기 위해서, KMP를 돌리면서 DP table을 채울 것이다. $N$개의 문자열에 대한 실패함수를 미리 구해놓고, 매칭 수 또한 $p_1, p_2, \cdots, p_N$로 $N$개를 사용한다. 이제 긴 문자열의 $i$번째 문자열까지 매칭시켰을 때 매칭이 완성된 짧은 문자열이 있다면 그 경우에 $dp_i=\max(dp_i, dp_{i-k}+k)$를 해주면 된다.

 

코드

#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define reset(x) memset(x, 0, sizeof(x))

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

const int MAX = 10101;
const int INF = 1e9;
const ll LINF = 1e18;

int F[505][MAX];

void get_fail(int x, string &t) {
    int p = 0, n = t.size();
    for(int i = 0; i < n; i++) {
        F[x][i] = 0;
    }
    for(int i = 1; i < n; i++) {
        while(p > 0 && t[i] != t[p]) p = F[x][p-1];
        if(t[i] == t[p]) p++;
        F[x][i] = p;
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);

    string s;
    cin >> s;
    int n;
    cin >> n;
    vector <string> t(n);
    for(int i = 0; i < n; i++) {
        cin >> t[i];
        get_fail(i, t[i]);
    }
    vector <int> dp(s.size()+1);

    vector <int> p(n);
    int L = s.size();
    for(int i = 0; i < L; i++) {
        dp[i+1] = max(dp[i+1], dp[i]);
        for(int j = 0; j < n; j++) {
            while(p[j] && t[j][p[j]] != s[i]) p[j] = F[j][p[j]-1];
            if(s[i] == t[j][p[j]]) p[j]++;
            if(p[j] == t[j].size()) {
                dp[i+1] = max(dp[i+1], dp[i+1-p[j]] + p[j]);
                p[j] = F[j][p[j]-1];
            }
        }
    }
    cout << dp[L];
}

 

KMP 자체도 유용하지만 접두사와 접미사가 같은 최대 길이를 모든 접두사에 대해 알려주기 때문에 부분 문자열과 접두사에 대한 관계 등이 중요한 문제에서 요긴하게 쓰인다. 다음과 같은 문제들을 간단하게 해결할 수 있다.

 

https://www.acmicpc.net/problem/16570

답

위 문제는 수열을 뒤집은 뒤 실패함수의 최댓값과 그 개수를 세기만 하면 된다.

 

https://www.acmicpc.net/problem/1498

답

$i$번째 문자까지의 접두사의 실패 함수를 $F_i$라 하면, $i-F_i$가 $i$를 나누고 몫이 2 이상일 때만(즉, $F_i$가 0이 아닐 때만) 주기도문임을 알 수 있다.

 

https://www.acmicpc.net/problem/1305

답

$n-F_{n}$이 답이다.

 

편의상 0-베이스로 코딩하였으나, 잘 보고 자기 입맛에 바꾸면 될 듯 싶다. 필자는 string으로 입력받은 뒤 이걸 바꾸는게 귀찮기도 하고 그래서 그냥 문자열 문자나 비트 관련 문제를 풀 때는 0-베이스를 선호하는 편이다.

 

그나저나 설명 부분 가독성이 영 꽝이라 그림이 가미된 다른 블로그를 봐도 이해가 잘 안 된다던가 할 때만 참고하는 편이 좋을 것 같다.