문자열검색 알고리즘. KMP

검색하면, 문자열비교함수 strcmp() 같은걸 떠올려서 O(m*n) 수준의 알고리즘을 사용하는게 딱 내 수준인데,

세상엔 이런 알고리즘들을 즐비하게 만들어내주신다. 저런 패턴을 찾아낸다는것 자체가 신비롭다.

나같은 범인들은 그냥 잘차려진 밥상에 숟갈 얹어 잘 먹어주기만 하면 되는데,

요즘처럼 호기심 왕성한 시기에는 하나하나 파헤쳐본다. 창조자의 기막힌 발상 자체에 경의를 표하며...

아래소스코드는 개략적인 아이디어를 확인하는 샘플코드. 의사코드로 된 것이 좀 더 정확하지만,

내 눈깔은 다른 언어보다 역시나 C/C++ 스타일에 너무 익숙하다. 때론 일상적인 언어보다 나을때가 있다.

--------------------------------------------------------------------------------

/*

 * KMP algorithm

 * KMP(char *s, char *p)

 * find string p in string s

 * if find p in s, return index of s

 * else return -1

 * set N (max string length)

 */

#include <cstdio>

#include <cstring>

#define N 100

using namespace std;

void make_f(char *p, int *f)

{

    int pl;

    int q, k;

    pl = strlen(p);

    f[0] = -1;

    k = -1;

    for( q=1; q<pl; ++q)

    {

        while( k>=0 && p[k+1] != p[q] ) k = f[k];

        if(p[k+1] == p[q]) k++;

        f[q] = k;

    }

}

int KMP(char *s, char *p) 

{

    int f[ N ];

    int sl, pl;

    int i, q;

    pl = strlen(p);

    sl = strlen(s);

    make_f(p, f);

    q = -1;

    for( i=0; i<sl; ++i)

    {

        while( q >= 0 && p[q+1] != s[i] ) q = f[q];

        if(p[q+1] == s[i]) q++;

        if(q == pl-1) return i-pl+1;

    }

    return -1;

}