KMP 알고리즘

KMP란?

문자열 a와 문자열 b가 있을 때 문자열 a에 문자열 b가 속해있는지 확인할 수 있고, 몇 개 있는지 확인하도록 도와주는 알고리즘입니다.

MS의 워드나 브라우져의 찾기 기능을 생각하시면 되겠습니다.

문자열 a에 문자열 b가 속해있는지 알고싶은지 확인하는 간단한 방법은 a의 배열 첫 번째부터 b의 문자열의 길이만큼 일치하나 확인하는 것일 겁니다. 이 경우, 최악의 경우 시간 복잡도는 O(nm)일 것입니다.

그러나, kmp를 사용하면 시간 복잡도를 O(n+m)으로 줄일 수 있습니다.

문자열 a를 "12341234.....", 문자열 b를 "12341235"라 가정해 봅시다.

일단 아까 말했던 간단한 방법대로 하면

문자열 a의 "1234123"와 문자열 "1234123"이 같은 것을 확인할 수 있을 것입니다.

kmp는 이 정보를 나중에 사용합니다.

(...)

다음은 kmp의 소스코드입니다. 저는 문자열 a와 문자열 b가 a[1], b[1] 부터 시작합니다. (원베이스)

k = 0;
for (int i = 2; i <= b_len; i++) {
    while (k > 0 && b[k + 1] != b[i]) k = p[k];
    if (b[k + 1] == b[i]) p[i] = ++k;
    else k = 0;
}
 
k = 0;
for (int i = 1; i <= a_len; i++) {
    while (k > 0 && b[k + 1] != a[i]) k = p[k];
    if (b[k + 1] == a[i]) {
        k++;
        if (k == b_len) res.push_back(i), k = p[k];
    }
    else k = 0;
}

문제보기: 백준1786-찾기