[Algorithm] Knuth-Morris-Pratt (KMP) 알고리즘
효과적인 설명을 위해 notation은 다음과 같다.x
: 찾고자 하는 문자열m
: x
의 길이y
: 본문의 문자열n
: y
의 길이
Morris-Pratt 알고리즘은 패턴 매칭을 하는데 유용한 알고리즘 중 하나다. Shift OR 함수처럼 매칭 시작전에 lookup table을 만드는 작업이 필요하다.
Lookup Table 만들기
void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; kmpNext[i] = j; } }
preKmp()
함수는 lookup table을 사전에 만드는 함수다. 내부엔 2중 while loop이 존재하는데, i
는 찾는 단어의 문자열 index, j
는 kmpNext
array의 index를 가리킨다. kmpNext
가 우리가 만들어야 하는 array인데, 이 값의 의미는 우리가 찾는 단어의 첫 단어부터 i
번째 단어까지 일치하는 접두사 – 접미사의 최대 길이를 말한다. 따라서 위 코드는 그 값을 나타낼 수 있도록 하는 알고리즘이다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-45.png)
먼저 찾고자 하는 단어가 ABCDABD라고 가정하고 설명한다.j
는 처음 -1로 시작하며 kmpNext[0]
값 또한 -1이다. 내부 while (j > -1 && x[i] != x[j])
를 만족시키지 못하기 때문에 i
, j
를 증가시키면서 현재 문자와 다음 문자가 다르기 때문에 kmpNext[1]
에 0을 저장한다. 만약 같다면 0이, 다르면 -1이 저장될 것이다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-42.png)
j는 0이 되면서 while (j > -1 && x[i] != x[j])
조건을 만족시면서 (x[0]
과 x[1]
이 다른 글자인지 확인), j
에 kmpNext[0]
인 -1을 다시 넣어서 초기값으로 돌아간다. 그리고 다시 i
와 j
의 index를 다시 증가시키면서 mpNext[2] = 0
을 수행한다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-46.png)
만약 3번째 단어가 1번째 단어와 같을 경우 어떻게 kmpNext
가 변하는지 보면, while문을 타지 않으면 j가 -1로 업데이트되지 않으면서 kmpNext[3]
에 1이 저장된다. 이 뜻은 첫 번째 단어와 index에 해당하는 마지막 단어가 1개가 일치한다는 뜻이다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-53.png)
다음과 다음다음 iteration도 동일하게 i가 1씩 증가하고 kmpNext[3]
, kmpNext[4]
의 값도 0이 저장된다. 그리고 다른 동작은 다음에 나타난다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-54.png)
while (j > -1 && x[i] != x[j])
를 만족하지 않기 때문에 j
를 업데이트하지 않고 넘어가면서 kmpNext[5]=1
이 수행된다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-55.png)
그리고 다음 index인 i가 D를 가리키게 될 때도 동일하게 수행되면서 kmpNext[6]
의 값은 2가 된다. 즉 D 이전까지 문자열에 접두사와 접미사가 동일한 문자의 길이는 2라는 의미다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-49-364x1024.png?v=1610865926)
마지막 iteration을 보면 x[i]
와 x[j]
가 다르기 때문에 while문을 통해서 j
는 -1로 돌아가고 kmpNext[7]
엔 0이 쓰이면서 함수가 종료된다.
Matching
이렇게 접두사, 접미사의 수를 기록해놓은 lookup table을 만든 이유는 우리가 불필요한 matching 동작을 줄이려고 하는 것이다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-58.png)
위 그림에서 y가 본문 문자열이라고 하면 6번째 글자가 일치하지 않는다고 했을 때, kmpNext의 값을 index 값에서 뺀 결과를 shift 수로 이용할 수 있다.
void KMP(char *x, int m, char *y, int n) { int i, j, mpNext[XSIZE]; /* Preprocessing */ preKmp(x, m, mpNext); /* Searching */ i = j = 0; while (j < n) { while (i > -1 && x[i] != y[j]) i = mpNext[i]; i++; j++; if (i >= m) { OUTPUT(j - i); i = mpNext[i]; } } }
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-66.png)
만약 위와 같은 문자와 본문을 KMP 함수를 통해 비교한다고 했을 때, while (i > -1 && x[i] != y[j])
는 계속 만족시키지 못했다가 틀린 문자가 찾아졌을 때 while구문을 수행한다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-67.png)
i
를 변경하면 위 그림처럼 x
전체가 shift 된 것 같이 된다. 즉 우리가 구한 shift 값인 6 – 2 = 4인 4칸을 뒤로 shift 한 것과 같은 동작을 수행한다. 즉 우리는 lookup table에 접두사와 동일한 접미사의 길이를 알기 때문에 해당하는 접미사부터 다시 비교를 시작하는 것이다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-68.png)
그리고 while문을 통해서 x
의 index인 i를 계속 옮겨주면서 x
를 밀어주면서 비교를 진행한다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-69.png)
MP to KMP
우리가 사실 지금 설명한 알고리즘은 정확히는 KMP의 이전 알고리즘인 MP (Morris-Pratt)에서 향상시킨 것이다.
void preKmp(char *x, int m, int kmpNext[]) { int i, j; i = 0; j = kmpNext[0] = -1; while (i < m) { while (j > -1 && x[i] != x[j]) j = kmpNext[j]; i++; j++; // kmpNext[i] = j; if (x[i] == x[j]) kmpNext[i] = kmpNext[j]; else kmpNext[i] = j; if(i > 6) { printf("i=%d, j=%d\n", i, j); display(kmpNext, m); } } }
위 코드에서 보면 kmpNext[i] = kmpNext[j];
부분이 추가된 것을 볼 수 있다. 이 차이는 lookup table을 만드는데 미리 비교를 하는 의미를 가진다. 즉 어차피 index를 비교해도 처음 match가 되지 않을 시에는 아예 첫 문자부터 비교를 진행해야한다는 기술이 담겨있다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-70.png)
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-71.png)
preKmp
함수에서 5번째 단어 A에 해당하는 kmpNext[4]
에 -1이 들어가고, kmpNex[5]
는 0이 들어간다.
![](http://shumin.co.kr/wp/wp-content/uploads/2021/01/image-72.png)
나중에 matching을 할 때는 kmpNext
의 값을 활용해서 iteration 수가 결정되는데, 수가 작으면 작을 수록 x
의 index 위치를 앞으로 당겨서 비교 수를 줄일 수 있다. 결과는 KMP 알고리즘이 더 시간을 줄이는데 이점을 가진다.
Reference
- https://m.blog.naver.com/kks227/220917078260
- http://www-igm.univ-mlv.fr/~lecroq/string