KnuthMorrisPrattAlgorithm

UserPreferences

1 개요

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

2 소스

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

3 링크

• Knuth-Morris-Pratt algorithm
  

• CategoryAlgorithm, CategoryTextProgramming