KMP 算法总结

之前看过关于kmp的文章好多次了 然后都忘了
这里简洁总结一下 方便下次快速想起

好开始，

A，B   两条string， 要稳B 到底有无match A其中一条substring.
关键就系整一个next 数组
系next 数组之前，先讲下
1. 最长公共元素长度， 具体自己体下图。

就是从该位置i结束的postfix (AjAj+1...Ai) 最多能与从0开始多长的prefix(A0A1..Ak) match到

当然 length(postfix) == length(prefix)

2.next 数组， 其实就是把上表数字往右移一格，index 0 值为-1 

用法：

字符不配对时 next数组告诉你从哪里重新开始 而不是总是跳回开头。

（参考资料里面噶3.3.2 可以参考下）

next 数组 生成方法：

void GetNext(char* p,int next[])  
{  
    int pLen = strlen(p);  
    next[0] = -1;  
    int k = -1;  
    int j = 0;  
    while (j < pLen - 1)  
    {  
        //p[k]表示前缀，p[j]表示后缀  
        if (k == -1 || p[j] == p[k])   
        {  
            ++k;  
            ++j;  
            next[j] = k;  
        }  
        else   
        {  
            k = next[k];  
        }  
    }  
}  

就是跳回去 再跳回去 直到回到原点或者匹配

int KmpSearch(char* s, char* p)  
{  
    int i = 0;  
    int j = 0;  
    int sLen = strlen(s);  
    int pLen = strlen(p);  
    while (i < sLen && j < pLen)  
    {  
        //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++      
        if (j == -1 || s[i] == p[j])  
        {  
            i++;  
            j++;  
        }  
        else  
        {  
            //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]      
            //next[j]即为j所对应的next值        
            j = next[j];  
        }  
    }  
    if (j == pLen)  
        return i - j;  
    else  
        return -1;  
} 

参考嘎资料
http://blog.csdn.net/v_july_v/article/details/7041827