KMP算法要解决的问题就是在字符串(也叫主串)中的模式(pattern)定位问题。说简单点就是我们平时常说的关键字搜索。模式串就是关键字(接下来称它为P),如果它在一个主串(接下来称为T)中出现,就返回它的具体位置,否则返回-1(常用手段)。
这里面的前缀集表示除去最后一个字符后的前面的所有子串集合,同理后缀集指的的是除去第一个字符后的后面的子串组成的集合。举例说明如下:
在“aba”中,前缀集就是除掉最后一个字符'a'后的子串集合{a,ab},同理后缀集为除掉最前一个字符a后的子串集合{a,ba},那么两者最长的重复子串就是a,k=1;
在“ababa”中,前缀集是{a,ab,aba,abab},后缀集是{a,ba,aba,baba},二者最长重复子串是aba,k=3;
在“abcabcdabc”中,前缀集是{a,ab,abc,abca,abcab,abcabc,abcabcd,abcabcda,abcabcdab},后缀集是{c,bc,abc,dabc,cdabc,bcdabc,abcdabc,cabcdabc,bcabcdabc},二者最长重复的子串是“abc”,k=3;
这里的p[j]==p[k],实际上就是指的从j=0开始,前缀与后缀相等的情况,一旦相等或k==-1,j&k同时加1,指向下一个元素,如果还相等,前缀与后缀依旧相等,next[j]也会随k增加而增加(j只增加而不会减少,而k在前缀与后缀不相等情况下会回溯,在if语句中k从0开始,满足条件逐步增加)
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;
}
标签:子串,字符,缀集,前缀,int,next,算法,KMP
From: https://blog.51cto.com/u_16030624/6196389