文档介绍：关于kmp算法改进的探讨
摘要:本文以模式串t是否有重复的几种不同情况的例子,分析了模式匹配算法kmp的形成过程,将较难理解的next函数的计算融入到算法中去,对算法做了一点改进,改进后的算法遵循kmp算法主串指针不回溯的原则新和主串s中该字符进行比较的字符位置。因此next函数的求解过程是kmp算法的关键,尽管next函数值可以用递归和next函数本身的定义出发对它进行计算,但其过程还是比较难理解,若加上其代码的形成过程,更是让众多初学者感觉是懂非懂,因此本文对kmp算法提出了一点改进,对于k值,不用next函数对其进行求解,而是把k值的计算融入到算法中去,主观上更容易理解其匹配过程,而代码看起来也更简洁易懂。
3 kmp算法的改进
改进的算法的过程如下:
(1)遵循kmp算法的指导思想,主串s与模式串t匹配时,当发生失配时,寻找下一个与s串失配字符匹配的t串字符时,主串s的下标i不回溯。
(2)主串字符s[i]与模式串字符t[j]匹配发生失配时,设置变量k使得主串s[k],(i-j+2<=k<i)与模式串的第一个字符t[1]进行一一比较,若匹配成功则把模式串t[1]移动到s[k]位置继续比较剩余字符,若不成功,则将t串t[i++]处的字符与模式串t的第一个字符进行下一轮的匹配,以此类推,直至结束。 (3)若模式串t的下标j大于模式串的长度时则表示在主串中找到了模式串。
其改进的算法代码如下:
输入一个字符串s为主串;
输入一个字符串t为模式串;
i=1;
j=1;
While (i<=len(s) && j<=len(t)) //len(s)为主串s长度,len(t)为模式串t的长度
{ if(s[i]=t[j])
{i++;
j++
}
else
{ k=i-j+2;
j=1;
I++;
While (k<I && j<len(t))
{if(s[k]==t[j])
{K++;
j++;}
Else
{k++;
j=1;
}
}
}
}
4 改進算法可行性
取主串s为qvqbqvcbdw,模式串t为qvcbd时,当初始值都为1时s[1]=t[1], i和j的值各加1,i=2,j=2,根据改进算法的程序,这样循环比较直至s[3] ≠t[3]时,重新置j=1,k=i-j+2=2,i加1后i=4,这时k的值小于i且j的值小于t串的长度,将t[1]的值与s[k]即s[2]的值进行比较后t[1]≠s[2],k值加1后k=2+1=3,j重新置1即j=1,这时k的值小于i且j的值小于t串的长度,将s[k]即s[3]与t[1]比较后s[3]=t[1],k的值加1即k=3+1=4,j的值加1后j=2,这时k的值不小于i,条件不满足,回到程序起始状态,将t串第二个字符与s串的第四个字符比较,s[i]即s[4]的值与t[2]的值进行比较,但s[4] ≠t[2],k的值为k=4-2+2=4, j重新置1即j=1,i的值加1后i=5,这时k的值小于i, 将s[