사용자 도구

사이트 도구


kb:knuthmorrisprattalgorithm

KMP

Knuth-Morris-Pratt String Matching Algorithm, 줄여서 KMP라고 불리는 문자열 검색 알고리즘. 어디에 사용할 수 있을까…

C++ Implementation

from http://jiniya.net

#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; 
} 

링크

kb/knuthmorrisprattalgorithm.txt · 마지막으로 수정됨: 2014/11/10 19:48 (바깥 편집)