사용자 도구

사이트 도구


kb:knuthmorrisprattalgorithm

차이

문서의 선택한 두 판 사이의 차이를 보여줍니다.

차이 보기로 링크

kb:knuthmorrisprattalgorithm [2014/11/10 19:48] (현재)
줄 1: 줄 1:
 +====== KMP ======
 +Knuth-Morris-Pratt String Matching Algorithm, 줄여서 KMP라고 불리는 문자열 검색 알고리즘. 어디에 사용할 수 있을까...
 +
 +
 +====== C++ Implementation ======
 +from http://​jiniya.net
 +
 +<code cpp>
 +#include <​stdio.h> ​
 +#include <​string.h> ​
 +#include <​stdlib.h> ​
 +
 +void failfunc(char *str, int *t) 
 +
 +    int len = strlen(str); ​
 +    int i, j; 
 +
 +    t[0] = -1; 
 +
 +    for(j=1; j<len; ++j) 
 +    { 
 +        i = t[j-1]; ​
 +
 +        while(*(str+j) != *(str+i+1) && i>​=0) ​
 +            i = t[i]; 
 +
 +        if(*(str+j) == *(str+i+1)) ​
 +            t[j] = i + 1; 
 +        else 
 +            t[j] = -1; 
 +    } 
 +
 +
 +int ffind(char *str, char *pat) 
 +
 +    int posp = 0, poss = 0; 
 +    int lenp = strlen(pat),​ lens = strlen(str); ​
 +    int *t; 
 +
 +    t = (int *)malloc(sizeof(int) * lenp); ​
 +    failfunc(pat,​ t); 
 +
 +    while((posp<​lenp) && (poss<​lens)) ​
 +    { 
 +        if(pat[posp] == str[poss]) ​
 +        { 
 +            ++posp; ​
 +            ++poss; ​
 +        } 
 +        else 
 +        { 
 +            if(posp == 0) 
 +                ++poss; ​
 +            else 
 +                posp = t[posp-1] + 1; 
 +        } 
 +    } 
 +
 +    free(t); ​
 +
 +    if(posp<​lenp) ​
 +        return -1; 
 +    else 
 +        return poss-lenp; ​
 +
 +
 +
 +int main() ​
 +
 +    char *s = "Hello wor;​lworld"; ​
 +    char *p = "​world"; ​
 +
 +    int n = ffind(s, p); 
 +
 +    printf("​%d",​ n); 
 +    return 0; 
 +
 +</​code>​
 +
 +====== 링크 ======
 +  * [[http://​en.wikipedia.org/​wiki/​Knuth-Morris-Pratt_algorithm | Knuth-Morris-Pratt algorithm]]
  
kb/knuthmorrisprattalgorithm.txt · 마지막으로 수정됨: 2014/11/10 19:48 (바깥 편집)