KMP算法 字符匹配
KMP是比较高效的一种字符匹配算法
在str中查找是否存在pattern
基本思想:
1. pattern的前i-1个与str[j-i+1]至s[j-1]字符匹配时，但pattern[i]与str[j]不匹配，用pattern[next[i]]与str[j]比较，无需从str[j-i+2]开始遍历。因为pattern的字符串本身可能有重复子串，这样就可以省略一些比较步骤。
例如pattern=“abababc”,str=”ababababcab”,str[6]与pattern[6]不匹配，我们只需比str[6]与pattern[4]是否匹配，而无须去比较从str[1]开始比较，因为在pattern[6]之前，“abab”重复，pattern的0~3与2~5相同
2. KMP主要解决的问题就在于求出next数组，next[i]的值取决于以pattern[0]开头的子串，能够与以pattern[i-1]结尾的子串匹配的字符个数。
用个类似正则表达式的形式：^pattern[0].*与.*pattern[i-1]$匹配的个数
例如pattern=“abcababc”
i 子串 next[i]
0 无 -1 /*哨兵用*/
1 “a” 0
2 “ab” 0
3 “abc” 0
4 “abca” 1 /*”a”与”a”*/
5 “abcab” 2 /*”ab”与”ab”*/
6 “abcaba” 1 /*”a”与”a”*/
7 “abcabab” 2 /*”ab”与”ab”*/
编程中几个要点
1. next[i]的值可通过next[i-1]来求解
2. 循环比较，若pattern[next[i]]与str[j]不匹配，比较pattern[next[next[i]]]与str[j]比较
3. 哨兵，next[0]=-1,若3中一直不匹配，当next值为-1时停止
void KMPnext(char *pattern,int *next,int length){int i=1,j;next[0]=-1;/*哨兵，显然s[0]的下一个比较元素是无，其他的next值都是>=0*/for(;i<length;i++){j=next[i-1];while(j>-1&&pattern[j]!=pattern[i-1])j=next[j];next[i]=j+1;}}int KMPfind(char*str,char*pattern,int*next,int length){int slen=strlen(str)+1;if(slen<length)return -1;int i=0,j=0;while(i<slen&&j<length){if(j<=-1||str[i]==pattern[j]){++i;++j;}else {j=next[j];}}if(j>=length)return i-length;elsereturn -1;}