Thursday, August 29, 2013

Knuth-Morris-Pratt Algortihm

String Matching : http://www.acmicpc.net/problem/1786

Pi[i] : 1부터 i번째까지의 부분 문자열에서 1 ~ k와 (i-k+1) ~ i까지가 같은 k값들 중 최댓값

#include <stdio.h>
#include <string.h>
#define MN 1000005
char T[MN], P[MN];
int pi[MN], sol[MN], sn, n, m;
int main() {
    int i, j, p;
    gets(T+1); n = strlen(T+1);
    gets(P+1); m = strlen(P+1);
 
    pi[0] = -1;
    pi[1] = 0;
    for (i = 2; i <= m; i++) {
        p = i-1;
        while (P[pi[p]+1] != P[i] && p >= 1) {
            p = pi[p];
            if (p <= 0)
                break;
        }
        pi[i] = pi[p]+1;
    }
    pi[0] = 0;
    j = 1;
    for (i = 1; i <= n; i++) {
        if (T[i] != P[j]) {
            p = pi[j-1];
            j = p+1;
            if (j == 1 && T[i] != P[j]) i++;
            i--;
        } else j++;
        if (j == m+1) {
            sol[++sn] = i-m+1;
            j = pi[j-1]+1;
        }
    }
    printf("%d\n",sn);
    for (i = 1; i <= sn; i++) printf("%d\n",sol[i]);
    return 0;
}
 
 
Pi 를 응용해서 푸는 문제 : http://www.acmicpc.net/problem/1787

No comments:

Post a Comment