백준 1786번 찾기 (boj/1786.c)

KMP 알고리즘 문제입니다.

#include <stdio.h>
#include <string.h>
#define MAX_N   1000002
char T[MAX_N] = { 0, };
char P[MAX_N] = { 0, };
int pi[MAX_N] = { 0, };
int res[MAX_N];
int main(void){
    int lenT, lenP;
    int cur, loc, cnt;
    fgets(T, MAX_N, stdin);
    fgets(P, MAX_N, stdin);
    lenT=strlen(T); lenP=strlen(P);
    lenT--; lenP--; T[lenT]=P[lenP]=0;
    pi[0] = -1;
    for(int i=1;i<lenP;i++){
        pi[i]=-1;
        for(cur=i-1;cur!=-1;cur=pi[cur]){
            if(P[i] == P[pi[cur]+1]){ pi[i]=pi[cur]+1; break; } }
    }
    loc=-1; cnt=0;
    for(cur=0;cur<lenT;cur++){
        if(loc == -1){
            if(T[cur] == P[0]){ loc=cur; }
            else{ continue; } }
        if(T[cur] == P[cur-loc]){
            if(cur-loc==lenP-1){
                res[cnt++] = loc+1;
                loc = (pi[cur-loc]!=-1)?cur-pi[cur-loc]:-1;
            } else{ continue; } }
        else{ loc = (pi[cur-1-loc]!=-1)?(cur-1)-pi[cur-1-loc]:-1; cur--; }
    }
    printf("%d\n", cnt);
    for(int i=0;i<cnt;i++){ printf("%d ", res[i]); }
    return 0;
}

 

이 알고리즘은 작성할 시 주의할 점이 몇 가지 있습니다.

• line 18: pi[idx]값이 항상 pi[idx-1]+1 또는 -1이 아니다. 즉, if(string[idx] == string[pi[idx-1]+1]) 에서 false가 뜨면 pi[idx-1]에서 재판단을 해줘야 한다. 당연히 시간복잡도는 O(M)이 아니다.
• line 24: loc==-1인 상황에서, T[cur]=P[0]이 떳을 때 바로 continue를 때리면 안 됩니다. P의 길이가 1인 상황을 고려해야 하기 때문. 이 경우에는 loc==cur이 성립하기 때문에 line31의 if문에 들어가면 아웃바운드가 뜬다고 할 수 있는데, 조건에 따라 T[cur]==P[cur-loc]가 항상 성립할 것이기 때문에 아웃바운드는 뜨지 않습니다.
• line 31: 만약, pi값이 -1이더라고, 현재 위치에서 재탐색을 한 번 해줘야 합니다. T=kaafg P=afg인 경우를 위해서입니다.