KMP( Knuth, Morris, Prett)

여기를 보면 기본 개념에 대해서 쉽게 익힐 수 있다. 본 글에서는 그럼에도 헷갈리는 점 위주로 써본다.

전체 문자열 텍스트T(길이 N)와, 찾으려는 패턴P(길이 M)가 있을때, 나이브하게 구현하면 $O(NM)$이 걸린다.

KMP를 사용하면 이를 $O(N+M)$으로 줄일 수 있다.

Pi함수(실패함수, 오버랩함수)

Pi함수는 위의 텍스트T와 패턴P중에서 패턴P에 대해서 미리 계산해놓는 함수이다. 실패함수라고도 하며, 문자열 매칭이 미스났을때 어디까지 back할지 정보를 제공한다.

pi[i]는 실패후에 앞부분에 이미 매칭한걸로 치는 오버랩구간을 의미하기 때문에 나는 오버랩함수라고 부른다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C

D

A

B

E

E

패턴

A

B

C

D

A

B

E

예를 들어 위와 같은 형태가 있을때, 6번 인덱스에서 불일치가 일어났는데 

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C

D

A

B

E

E

패턴

A

B

C

D

A

B

E

위와 같이 텍스트에서 불일치가 발생한 C왼쪽 부분에서 이미 매칭한걸로 치는 오버랩 구간은 최대한 길게 잡았을때 AB임을 알 수 있다. 

좀더 길게 DAB로 잡고 싶어도 패턴이 D로 시작하지 않는다. 아예 ABCDAB로 잡으려고 하면 이미 실패한 패턴이고 제자리걸음이라 택할수 없다.

인덱스

0

1

2

3

4

5

6

7

8

9

10

11

텍스트

A

B

C

D

A

B

C

D

A

B

E

E

패턴

A

B

C

D

A

B

E

따라서 위와 같이, 텍스트의 C왼쪽 postfix AB와 패턴의 prefix AB를 위처럼 오버랩시키고 나면 인덱스 6부터 다시 비교를 시작하면 된다.

오버랩함수가 2일때 패턴을 보면 오른쪽으로 6-2=4칸 점프(?)한걸 볼 수 있는데,

이처럼 오버랩함수의 값이 오히려 작으면 작을수록 점프를 많이한다.

오버랩함수가 5이면 6-5=1이라서 한 칸만 오른쪽으로 이동한다.

오버랩이 많이 되면 오른쪽이동량은 적은대신 이미 많이 오버랩되어 있으므로 적게 추가로 매칭되면 매칭이 완성되는 장점이 있으므로 무조건 오버랩이 적게되서 오른쪽으로 점프를 많이 하는게 좋은건 아니다.

그래서 pi[i]는 주어진 문자열의 0~i 까지의 부분 문자열 중에서 최대 prefix == suffix길이로 세팅한다.

문자열 "ABAABAB"의 pi배열을 구해봅시다.

i	부분 문자열	pi[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAA	1
4	ABAAB	2
5	ABAABA	3
6	ABAABAB	2

팰린드롬 개념이 아님에 주의!

문자열 "ABABABC"의 pi배열을 구해봅시다.

i	부분 문자열	pi[i]
0	A	0
1	AB	0
2	ABA	1
3	ABAB	2
4	ABABA	3
5	ABABAB	4
6	ABABABC	0

prefix와 posfix가 오버랩되도 문제없음에 주의(위의 초록색 글자)

이해하기는 쉽지만, 효율적으로 $O(M)$에 pi함수를 구하는건 약간 어렵다.

그래도 맨위 링크를 통해 공부하고 아래와 같은 함수를 짤 수 있었다.

using vi = vector<int>;
vi getPi(string p) {
    int m = (int)p.length();
    vi pi(m);
    for (int j = 0, i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}

오버랩을 while로 여러번 적용하는 케이스가 발생하는 것은 아래를 참조하자.

불일치 발생

오버랩 함수 1차적용

오버랩 함수 2차 적용

오버랩함수 3차적용

"AABAAA"에 대해서 Pi를 구해보면 Pi = {0,1,0,1,2,2} 이렇게 나오는데 중간에 0이 섞이기도 하고 마지막 2가 찍힐때 내가 원하던 조금 복잡한 다이나믹이 나오니 필요하면 검토해보자.

Pi함수가 갖는 오버랩의 의미에 대해서는 백준 1305 광고 문제를 풀어보면 직접적인 도움이 된다.

KMP

Pi함수를 이해했다면 KMP는 이를 이용해서 어렵지 않게 아래와 같이 짤 수 있다.

(물론 스크래치부터 짜면 구현실수를 많이 포함되게 된다. 대략적인 흐름만 이해하고 복사해서 쓰자)

이 문제의 답안이기도 하다.

#include <bits/stdc++.h>
using namespace std;
 
using vi = vector<int>;
vi getPi(string p) {
    int m = (int)p.length();
    vi pi(m);
    for (int j = 0, i = 1; i < m; i++) {
        while (j > 0 && p[i] != p[j]) j = pi[j - 1];
        if (p[i] == p[j]) pi[i] = ++j;
    }
    return pi;
}
//p가 발견된 위치들을 리턴(0 base)
vi KMP(string t, string p) {
    int n = (int)t.length(), m = (int)p.length();
    vi pi = getPi(p);
    vi r;
    for (int i = 0, j = 0; i < n; i++) {
        while (j > 0 && t[i] != p[j]) j = pi[j - 1];
        if (t[i] == p[j]) {
            if (j == m - 1) 
                r.push_back(i - m + 1), 
                j = pi[j];  //j=0이 아님에 주의(오버랩고려)
            else j++;
        }
    }
    return r;
}
 
int32_t main()
{
    ios::sync_with_stdio(0); cin.tie(0);
 
    string t, p;
    getline(cin, t), getline(cin, p);
    vi v = KMP(t,p);
    cout << v.size() << '\n';
    for (auto a : v)cout << a + 1 << ' ';
    cout << '\n';
    return 0;
}