以前看kmp算法没有重视,如今发现当时的理解存在一些问题。 说kmp算法,先要说一般的匹配算法 一般匹配算法就是以keyword的首字母为标记。匹配过程遇到不匹配,标记移动到下一位,重新与文本串匹配。当keyword只有一个字母时,效率是一样的,但当keyword较长,极端情况是keyword自己本身没有重复字母,匹配过程中遇到文本子串与keyword最后一位不匹配时,我们自己心里清楚,完全没必要让标记只移动一位,可以整个移动keyword(length)-1位
char[] | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | …… |
---|---|---|---|---|---|---|---|---|---|
text | a | b | c | d | e | a | a | b | …… |
key | a | b | c | d | e | f | … |
当然这种情况我们心里清楚,下一步完全可以直接比较key[0]和text[5]。
我们希望能将比较过的过程尽量不要重复,利用比较过的结果
当比较到 key[j]!= text[i] 时 说明key[0,j-1]==text[i-j,i-1]。
我们最希望的状态是 j直接回到0继续和text比较。
但当出现 key[0,,k]==key[(j-1)-k,j-1],时,且text[i]==key[k],我们必须从i,k处继续比较,以避免忽视这种匹配。
i | i | ||||||||
---|---|---|---|---|---|---|---|---|---|
text | a | b | c | a | b | c | a | b | …… |
key | a | b | c | a | b | a | … | ||
j | j | ||||||||
char[] | 0 | 1 | 2 | 3 | 4 | 5 | … |
上表中k为2,
k就是key的子串key[0,j-1]中前后缀相等的最大长度。(因为数组下标从0开始,比较的是相等串的后一个字母,恰恰是key[k])。
以abcaba为例
abcaba | 0,j-1子串的前后缀 | k |
---|---|---|
j=0 可以理解成j前面有几个元素 |
j-1=-1 这就是一些kmp算法设置next[0]=-1的原因 |
0 |
j=1 | a | 0 |
j=2 | ab | 0 |
j=3 | abc | 0 |
j=4 | abca | 1 |
j=5 | abcab | 2 |
kmp算法中next[j] 就是key[j]对应的k。next的值可以通过key[]的自我比较来确定,如果已知next[i]=k,即必有key[0,k]==key[i-k,i],则当key[i+1]=key[k+1]时,next[i+1]=k+1;否则找key[0,k]内的重复子串,此时可比较key[next[k]]==key[i+1] (相当于使用已知next[]搜索,跟kmp思想是一样的)。
于是就有kmp算法
//kmp主体,本代码只体现思想,并不考虑应用场景
int KMP(Str text,Str key,int next[])
{
int i=0,j=0;
while(i<text.length && j<key.length)
{
if(text.ch[i]==key.ch[j])
{++i;++j;}
else
{
j=next[j];
if(j==0)++i;
}
}
if(j>=key.length)
return i-key.length;//若继续搜索可以把结果先存入数组
else return -1;
}
//生成next数组
void getnext(Str key,int next[])
{
int i=1,k=0;
next[0]=0;//初始化
next[1]=0;
while(i<key.length)
{
if(key[i]==key[k])
{
next[++i]=++k;//next[i+1]=k+1
}
else
k=next[k];//回溯对比key[next[k]]?=key[i]
}
}