KMP, Features of fail function
KMP(Knuth-Morris-Pratt) 알고리즘, 단일 문자열 패턴 매칭
위 세 사람이 힘을 합쳐(?) 알고리즘을 고안해냈기에 KMP란 이름이 붙었다.
찾으려는 문자열 $F$가 어떤 문자열 $S$ 안에 있는지 $O(\vert{F}\vert +\lvert{S}\rvert)$에 찾을 수 있는 알고리즘이다.
한 때, Solved.ac 기준 골드 1에 있던 알고리즘이였으나 플레티넘 5로 난이도가 올라버렸다.
충분히 그럴만하고 성질이 처음 접한다면 LCA같은 트리 날먹 플레 알고리즘보다 이해하기에 간단하지 않다(고 개인적으로 생각한다).
KMP의 실패 함수의 정의
문자열 패턴매칭에서 실패 함수란건 아호-코라식에도 등장하는 개념일 정도로 중요하다.
현재 위치에서 해당 문자가 더 이상 매칭이 될 수 없을 때, 처음부터 다시 검사하는 것이 아닌 가장 될 것 같은 위치로 이동을 하여 검사를 진행하게 만들고, 이것이 알고리즘이 $O(N)$이 되게하는 핵심이다.
KMP에서의 실패함수란 다음과 같다.
$ \qquad {\it fail}_{\textstyle i}$ = 문자열 $F$의 $[0, i]$ 범위의 부분 문자열 $F’$ 에서 최대로 일치하는 prefix와 suffix의 길이
단, prefix와 suffix의 길이가 같으면 안된다. 그래서 $\rm fail_0=0$ 인 것이다.
표로 나타내보자.
ABABABDA 라는 문자열이 있다고 하자.
그럼 위와 같이 실패 함수가 만들어진다.
| A | B | A | B | A | B | D | A | |
|---|---|---|---|---|---|---|---|---|
| $\it i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| $\it fail_{\,i}$ | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 1 |
KMP 실패 함수 구현
코드는 간략하다.
vi kmp_fail(const string &s) {
vi fail(sz(s));
for (int i = 1, j = 0; i < sz(s); i++) {
while (j && s[i] != s[j]) j = fail[j - 1];
if (s[i] == s[j]) fail[i] = ++j;
}
return fail;
}
시간복잡도를 먼저 보자면, $i$는 $s$의 길이만큼 돌고, $j$는 한번의 루프에서 최대 1 증가하고 감소하는 while 에 걸려도 0이 되면 while문을 탈출하므로 결국 $O(N)$이 된다.
ABABABDA 를 가지고 얘기를 계속해보자.
코드가 간단하지만 이걸 오랜만에 보거나 처음보면 뭔코드지 싶은데, 조금 자세히 살펴보자.
$i$는 1, $j$는 0부터 시작한다.
일단 처음에 while문은 지나치고 $s_1$과 $s_0$을 비교하는데, 다르므로 $\it fail_1$은 0이 담긴다.
이 비교하는 과정은 이렇게 보고 비교한 것과 같다.
ABABABDA
ABABABDA
B와 A는 다르다.
ABABABDA
ABABABDA
$i$ = 2 일 때는 문자가 같으므로 $j$는 1이 되고 $\it fail_2$도 1이 된다.
ABABABDA
ABABABDA
$i$ = 3 일 때, 또한 같으므로 $j$는 2가되고 $\it fail_3$도 2가 된다.
ABABABDA
ABABABDA
$i$ = 4 일 때, $j$는 3이되고 $\it fail_4$도 3이 된다.
ABABABDA
ABABABDA
마찬가지로 $j = \it fail_5 = \rm4$ 이다.
ABABABDA
ABABABDA
이제 $j$는 while문 조건에 걸린다. $j = \it fail_{\rm 4-1}$ 이 되므로 $\it fail_{\rm 3}$ 인 2가 $j$가 된다.
이 경우를 유심히 살펴보자. $j$가 2가 된 다음 하게될 검사는 다음과 같다.
ABABABDA
ABABABDA
또 다르므로 $j$는 결국 while문을 돌다 $0$이 되어서 $\it fail_{\rm 6}\rm = 0$이 될 것이다.
그런데 이렇게 $j$가 $\it fail_{\rm \,\,j-1}$ 로 돌아가며
ABABABDA
ABABABDA
$\qquad \downarrow$
ABABABDA
ABABABDA
이렇게 검사를 하는 과정을 살펴보면, 처음에는 ABABA의 매칭이 실패했다. 그러면 제일 뒤의 A가 맞지 않는다는건데, 처음으로 돌아가는 것이 아니라 ABA 를 매칭해보려고 시도함을 알 수 있다.
이것이 바로 실패함수와 KMP 알고리즘 전반적으로 걸쳐있는 중요한 성질인데, 어떤 문자를 매칭하려다가 실패를 했을 때,지금까지 일치했었던 부분 문자열에서의 suffix와 일치하는 가장 긴 prefix와의 길이를 알고있다면,
그만큼은 스킵해주고 바로 가장 최적의 위치로 옮겨서 검사를 진행해갈 수 있다는 것이다.
추가 설명 1 - 인덱스 $i$ 와 $j$ 의 의미
좀더 복잡한 예시와 자세한 설명은 다음과 같다.
일단 코드상에 있는 $i$ 와 $j$ 가 어떤 의미를 갖는지를 살펴볼 필요가 있다.
실패 함수를 만드는 과정은 $S$와 $S$ 자기 자신을 계속 비교하는 문자들의 인덱스를 적절히 변경시키는 과정임을 인지하자.
$i$와 $j$ 모두 $S$ 에서 현재 가리키고 있는 문자 그 자체를 의미한다.
$S$ = ABABDDABAB 라고 해보자.
예를 들어 $i=5,~j=3$ 라고 한다면,
ABABDDABAB $i$
ABABDDABAB $j$
두 인덱스를 비교하고 있다는 뜻이다. 항상 $i>j$ 이므로 아래쪽 부분이 더 오른쪽으로 가있다고 볼 수 있다.
여기서 $j$ 가 감소한다는 것은 아래쪽 줄이 오른쪽으로 밀린다는 것을 뜻한다. 예를들어 $j=3$ 에서 $j=1$ 로 감소한다는 것은 다음과 같은 결과가 된다.
ABABDDABAB $i$
ABABDDABAB $j$
추가 설명 2 - 복잡한 예시
실패함수의 코드를 이해하는 것은 쉽게 혼동이 오는데, 인덱스가 $0-based$ 인가 $1-based$ 인가에 따라 헷갈리기 때문이다.
복잡한 예시를 들어 $0-based$ 로 설명해보겠다.
$S$=AABAACAADAABAABA 라고 하자.
처음에 $i=1,~j=0$ 상태로 시작하므로
AABAACAADAABAABA $i=1$
AABAACAADAABAABA $j=0$
맞았으므로 $f_1=1$ 이다.
| A | A | B | A | A | C | A | A | D | A | A | B | A | A | B | A | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f$ | 0 | 1 |
AABAACAADAABAABA $i=2$
AABAACAADAABAABA $j=1$
틀렸으므로 $j$는 $f_{j-1}=0$ 으로 돌아간다.
| A | A | B | A | A | C | A | A | D | A | A | B | A | A | B | A | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f$ | 0 | 1 | 0 |
AABAACAADAABAABA $i=3$
AABAACAADAABAABA $j=0$
다시 맞았으므로 $j=1$ 이 된다.
| A | A | B | A | A | C | A | A | D | A | A | B | A | A | B | A | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f$ | 0 | 1 | 0 | 1 |
AABAACAADAABAABA $i=4$
AABAACAADAABAABA $j=1$
또 맞았다. $j=2$ 가 된다.
| A | A | B | A | A | C | A | A | D | A | A | B | A | A | B | A | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f$ | 0 | 1 | 0 | 1 | 2 |
AABAACAADAABAABA $i=5$
AABAACAADAABAABA $j=2$
여기서 틀렸으므로 $j=f_{j-1}$이 되고, 이는 $j=1$ 이 되게한다.
그런데 지금까지와 다르게 $j=0$ 으로 변한게 아니다.
이는 다음과 같은 검사를 하게 되었다는 것을 의미한다.
AABAACAADAABAABA $i=5$
AABAACAADAABAABA $j=1$
왜 이렇게 되었을까?
$S_i$ 와 $S_j$ 가 같은지를 검사하는 시점에 $j$ 의 값은 무엇을 의미할까?
사실 앞선 설명에서 $j$ 도 그저 $S$ 에서 $S$ 를 검사하고 있을 때 인덱스 중 하나라고 했는데, 이 설명도 맞지만 더 중요한 사실은, $S_i$ 와 $S_j$ 를 비교하고 있는 시점에 $[i-j,\,i-1]$ 와 $[0,\,j-1]$ 이 일치하고 있다는 것이다.
사실 여기까진 당연하다고 생각할 수 있다. 그러나 여기서 실패함수의 정의를 다시 곱씹어보자.
실패함수 $fail$ 을 이용하면 바로 저 $[i-j,\,i-1]=[0,\,j-1]$ 구간에서 최대로 일치하는 prefix와 suffix의 길이를 이용해 그 다음 비교하게 될 자리를 가장 합리적으로 결정할 수 있다는 것이다.
조금 빠르게 진행시켜서 이제 여기를 비교하고 있다고 하자.
현재 $i=14$ 이고 $j=5$ 이다.
| A | A | B | A | A | C | A | A | D | A | A | B | A | A | B | A | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f$ | 0 | 1 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 |
AABACAADAABAABA $i=14$
AABAACAADAABAABA $j=5$
여기서 틀렸는데, 앞에 AABAA이 같음을 볼 수 있다. 근데 여기서 prefix와 suffix에서 같은 부분 중 가장 긴 길이는 $fail_4=2$ 니까 우린 다음과 같이 처음부터 비교를 시작해주는게 아니라
AABACAADAABAABA $i=14$
AABAACAADAABAABA $j=0$
다음과 같이 가장 효율적으로
AABACAADAABAABA $i=14$
AABAACAADAABAABA $j=2$
검사를 해줄 수 있음을 의미한다.
$f_{5-1}=2$ 니까 다시 $j=f_4=2$ 값으로 돌아왔다.
AABAA 에서 가장 긴 일치하는 prefix와 suffix의 길이가 2이므로 $j$ 를 2로 보내도 문제가 없는 것이다.
왜냐? 0-based에선 j=2 가 곧 두개를 건너뛰고 세 번째 자리부타 검사를 다시 시작하겠다는 것을 의미하니까!
이렇게 $j$ 가 $j=f_{j-1}$ 로 돌아가는 과정은 하나의 $i$ 당 최대 한번만 일어나는것이 아닌 $S_i \ne S_j$ 일 때 $j>0$ 일 때까지 계속해서 반복된다는 사실에 유의하자.
결국 여기선 B가 일치해
| A | A | B | A | A | C | A | A | D | A | A | B | A | A | B | A | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| $f$ | 0 | 1 | 0 | 1 | 2 | 0 | 1 | 2 | 0 | 1 | 2 | 3 | 4 | 5 | 3 | 4 |
이런식으로 테이블이 완성된다.
KMP 구현
KMP는 구현만 바로 살펴볼건데, 위에서 실패함수가 무엇이고 실패함수가 만들어지는 과정과 실패함수의 쓰임성을 이해했다면 KMP 알고리즘 자체는 거의 똑같게 동작하기 때문이다.
vi kmp(const string &a, const string &b) {
vi fail = kmp_fail(b), match_indice;
for (int i = 0, j = 0; i < sz(a); i++) {
while (j && a[i] != b[j]) j = fail[j - 1];
if (a[i] == b[j]) {
if (j == sz(b) - 1) {
match_indice.push_back(i - sz(b) + 1);
j = fail[j];
} else {
j++;
}
}
}
return match_indice;
}
시간복잡도는 b의 실패함수를 찾는데 $O(\lvert b \rvert)$, $i$는 $\lvert a \rvert$ 만큼 증가하고 실패함수에서와 같은 이유로 $j$는 한 루프당 최대 1 증가하기 때문에 $O(\lvert a \rvert + \lvert b \rvert)$ 이다.
a에서 b가 있는지 찾고 싶은 것이고, 일단 b의 실패 함수를 만든다.
이후 a의 인덱스 $i$와 b의 인덱스 $j$를 0부터 시작해서 실패함수 생성과 코드가 유사하다.
원리도 똑같다.
여기서 왜 $j$가 |b| - 1 이 되었을 때(일치하는 문자열을 찾았을 때), $j = \it{fail}_{\,j}$ 가 되는지만 짚고넘어가자.
ABCDABCDABCDABCD
ABCDABCD
요렇게 찾아졌다고 하자. 그럼 지금 $j=7$일 것이다. ${\it fail}_7 = 4$ 일 것이므로 이제 그 다음 비교는 다음과 같이 비교하는 것이 된다.
ABCDABCDABCDABCD
ABCDABCD
실패함수를 만들때 봤던 것처럼 b 자기 자신의 가장 긴 prefix, suffix가 동일한 것의 길이를 알기 때문에 그만큼(4) skip 하고 비교를 시작할 수 있는 것이다.
이 때, $j$를 무조건 ${\it fail}_j$ 로 만들어야 KMP가 제대로 동작함에 유의하자.
$j$를 0으로 만들거나 하면 알고리즘이 제대로 동작하지 않아 정답을 구할 수 없고 시간복잡도도 보장될 수 없다.
KMP 실패함수의 성질들 ⭐️
위와 같은 내용을 알면 KMP 기본 문제들을 날먹날먹 할 수 있지만, 응용 문제는 실패함수의 성질을 묻는 문제들도 있다.
실패함수의 성질을 공부하면서 개인적으로 정말 신기했다.
아래부터 글들이 1-based 로 작성되어 있는데, 구현을 한다면 필요에 따라 0-based 로 적절히 인덱스 조절을 해주도록 하자.
실패함수의 성질 1 - Prefix 이면서 동시에 Suffix인 것들의 길이는
$\it fail_N$
$\it fail_{fail_N}$
$\it fail_{fail_{fail_N}}$
$\it fail_{fail_{fail_{fail_N}}}$
$\cdots$
$\it fail_N$, $\it fail_{fail_N}~\cdots$ 을 반복하면 prefix에도 있고 suffix에도 있는 문자열들을 모두 순회할 수 있다.
이게 어떻게 가능한것일까?
일단 $\it fail_N$ 부터 시작해야한다. 왜냐면 온전한 문자열을 이용해 계산을 한 것은 $\it fail_N$ 밖에 없기 때문이다.
$\it fail_N$ 의 길이가 $T$ 라고 해보자.
원 문자열에서 $[1, T] = [N - a + 1, N]$ 은 동일할 것이다.
예를 들어보자.
| a | b | c | a | b | c | a | b | c | |
|---|---|---|---|---|---|---|---|---|---|
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| $\it fail$ | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
위와 같이 인덱스와 실패 함수가 정해지는데, ${\it fail}_9 = 6$ 이다.
그렇다면 $[1, 6]$과 $[4, 9]$ 가 일치함을 알 수 있고, 그 다음 prefix와 suffix가 같은 문자열은 $[1, 6]$ 안에서 있을 것임을 알 수 있다.
왜냐하면 $[1, 6]$ 그 자체로 prefix 이며 suffix이기 때문에 그 다음으로 짧은 동일한 prefix와 suffix도 $[1, 6]$ 에서 찾을 수 있다.
그리고 그 값은 바로 $\mathit{fail}_6 = 3$ 이다.
$[1, 6]$ 그 자체로 실제 문자열의 prefix, suffix와 동일해서, $[1, 6]$ 을 이용해 $\it fail$ 함수를 구한 값이 실제 문자열에서도 prefix와 suffix를 의미한다.
실패함수의 성질 2 - “$L$ 길이의 반복되는 패턴이 나오고 있다” 와 $L = i - \mathit{fail}_i$ 는 동치이다.
이게 뭔소린가 싶었는데, abcdefabcdzz 라는 문자열을 보자.
| a | b | c | d | e | f | a | b | c | d | z | z | |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| $\it fail$ | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 0 | 0 |
$i = 9$ 을 보자.
$L = 9 - 3$
즉, $L = 6$ 이다.
실제로 문자열에서 6자리의 패턴이 $i = 1$ 부터 반복되기 시작하는가?
그렇다. abcdef 가 반복되고있다.
실제로 abcdef 가 반복되지 않는다는 것을 알 수 있지만, $i = 9$ 인 시점에서는 abcdef + abc 이므로 그것이 “나오고 있다” 라고 표현한 것이다.
왜 이게 가능할까?
${\it fail}_n = T$ 라고 해보자.
역시나 $[1, T]$ 와 $[n - T + 1, n]$ 은 같다.
케이스를 나눠보자.
- $2T = n$ 인경우
그러면 딱 절반으로 나뉘는 경우이므로, 패턴이 당연히 존재한다.
- $2T \lt n$ 인경우
abczabc 의 예시를 보자.
| a | b | c | z | a | b | c | |
|---|---|---|---|---|---|---|---|
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| $\it fail$ | 0 | 0 | 0 | 0 | 1 | 2 | 3 |
$i = 7$ 을보면,
앞에 3개와 뒤에 3개가 같고,
뒤에 3개를 제외한 abcz 가 패턴이 반복되고 있다. 그러므로 이 경우 $L = 7 - fail[7] = 4$ 짜리 패턴이 반복되고 있다.
- $2T > n$ 인 경우
| a | b | c | a | b | c | a | b | c | |
|---|---|---|---|---|---|---|---|---|---|
| $i$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| $\it fail$ | 0 | 0 | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
$i = 9$ 를보면, $\mathit{fail}_9=6$이다.
그러면 $9 - 6 = 3$ 짜리의 패턴이 존재할 가능성이 있다 라고 판단이 된다.
$[4, 6]$이 $[1,3]$과 $[7,9]$의 $k$번 반복된 꼴임을 어떻게 알까?
$[1, 3] = A, \,[4, 6] = B,\, [7, 9] = C$ 라고 하자.
$A = C$ 임을 알고있다.
또한 실패 함수의 정의에 의해 $A + B = B + C$ 이다.
즉, $A + B = B + A$ 가 된다.
우리의 결과대로라면 $A$와 $B$가 교환 법칙이 성립함을 알 수 있는데,
$B$가 $A$의 $k$배 꼴이라는 것은 $A$와 $B$의 교환법칙이 성립한다의 충분조건이기 때문에
문자열끼리의 교환 법칙 성립하기 위한 필요 충분 조건은 $A$와 $B$가 동일한 문자열의 $k$배 여야 한다는 것을 다음과 같은 사이트에서 알 수 있었다.
또한 3번째 항목을 보면 $B$는 무조건 $kA\, \footnotesize (k \ge 1)$ 여야 한다.
린던 슈텐베르크 정리에 의해 이러한 일반화를 보일 수 있다고 한다.
${\it fail}_i = 0$ 인 경우에도 이 정리는 성립한다.
아직 하나의 반복도 되지않은 패턴이 이어지고 있다고 생각할 수 있기 때문이다.
문제 풀이: BOJ 16229 - 반복 패턴
그리고 다음과 같은 문제를 풀어보자.
void solve() {
...
int i = fail[n - 1], ans = 0;
while (i) {
int pattern_len = n - i;
int times = (n + k) / pattern_len;
if (times >= 2 && pattern_len * times >= n) {
ans = max(ans, pattern_len);
}
i = fail[i - 1];
}
cout << ans;
}
0-base $\it fail$ 함수이므로 $\it fail$ 배열의 인자에 -1 들이 들어가있다.
위에서 설명한 것과 같이, 패턴이 반복되는 길이를 나누기 연산을 통해 구하고, 이 횟수가 2번 이상이고 실제 문자열보다 긴 경우에 답을 갱신해줄 수 있다.
Comments