KMP (Knuth-Morris-Pratt)

문자열 찾기 알고리즘(String matching algorithm), 시간 복잡도는 O(N+M) 이다.

코드

#include <stdio.h>
#include <string.h>
#include <vector>

using namespace std;

int pi[1000010];
vector<int> pos;

void get_pi(char *p)
{
    int i, j;

    for (i = 1, j = 0; p[i]; i++) {
        while (j > 0 && p[i] != p[j])
            j = pi[j - 1];
        if (p[i] == p[j])
            pi[i] = ++j;
    }
}

int kmp(char *w, char *p)
{
    int i, j, find = 0, plen = strlen(p);

    for (i = 0, j = 0; w[i]; i++) {
        while (j > 0 && w[i] != p[j])
            j = pi[j - 1];
        if (w[i] == p[j]) {
            if (j == plen - 1) {
                find++;
                pos.push_back(i - plen + 2);
                j = pi[j];
            }
            else
                j++;
        }
    }

    return find;
}

int main()
{
    char t[1000010], p[1000010];

    gets_s(t);
    gets_s(p);

    get_pi(p);
    printf("%d\n", kmp(t, p));
    for (int p : pos)
        printf("%d\n", p);

    return 0;
}

1786 찾기에 대한 코드

정리

  • 실패 함수(failure function)는 접두사 == 접미사 의 최대 길이를 의미한다.
  • 예를 들어 ABCAB 이면 pi[4] = 2 이다 (AB 이므로), ABABA 의 경우 pi[4] = 5이다 (ABABA)
  • 문제의 유형
    • KMP 를 이용한 문자열 탐색
    • 실패 함수의 성질을 이용하는 문제
  • Boyer-Moore 알고리즘이 kmp 보다 더 성능이 좋다고 한다. (하지만 정말 대회에 나올까?)

관련 문제

참고 자료

results matching ""

    No results matching ""