kmp算法

#include <stdio.h>
#include <string.h>
#include <malloc.h>

void fail(int f[], char* p)
{
//模式的长度
    int n = strlen(p);
    //需要两个循环变量
    int i;
    int j;
    //根据公式, 第一个初始化为1
    f[0] = -1;
    //对剩下的1~n-1下位置求f[j]
    for( j = 1; j < n; j++ )
    {
     //根据递归公式f(j) = f(j-1) + 1, 将i初始为f(j-1)
        i = f[j-1];
        while( *(p+j) != *(p+i+1)  //判断是否符合f(j)的定义
            && i >= 0 )    //i < 0的话,下面的f[i]就不对了
            i = f[i];
        //判断是因为 i < 0 而退出循环到这里,还是因为找到符合f(j)定义的位置而到这里的.
        //判断之后,再定义赋值
        if( *(p+j) == *(p+i+1) )
            f[j] = i + 1;
        else
            f[j] = -1;
     }
}

int kmp(char* t, char* p)
{
   // 需要两个记录长度, 两个用于遍历
   int lt = strlen(t);
   int lp = strlen(p);
   int pt = 0, pp = 0;
   // 关键的数组
   int* f = malloc(lp);
   fail(f, p);
   // pt=lt表示pt已经指向目标的\0字符,即找不到模式了
   // pp=lp表示pp已经指向模式的\0字符,即已经找到模式
   while( pt < lt && pp < lp )
   {
    //如果当前字符匹配,则移动位置指针pt和pp
        if( *(t+pt) == *(p+pp) )
        {
            pt++;
            pp++;
        }
        //就算当前字符不匹配,目标的位置也不用回溯,每次比较,目标的位置都是要向前移1的
        //目标的位置可能在上面的if里面移了1位,但是如果pp=0且不匹配的话,
        //则上面if里的语句没执行, 所以这里要把目标的位置向前移1
        else if( pp == 0 )
            pt++;
        //如果pp != 0, 则将pp回溯
        //这里pp肯定是满足pp != 0的时候, f[pp-1]就不会引用了负数下标了
        //pp要减1, 是因为pp != 0时, 最上面那个if里把pp向前移动了1
        else
            pp = f[pp-1] + 1;
   }

   free(f);

   if( pp < lp )
        return -100;
   else
        return pt - lp;
}

int main()
{
    char* p = "123";
    char* t = "0145123921";
    int index = kmp(t, p);
    printf("p=%s, t=%s,index= %d\n", p, t, index);
}

转载请注明出处 http://fornote.blogspot.com