如何通过Java代码实现KMP算法
这篇文章主要介绍了如何通过Java代码实现KMP算法,文中通过示例代码介绍的非常详细，对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）。KMP算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个next()函数，
函数本身包含了模式串的局部匹配信息。时间复杂度O(m+n)。
代码如下
importjava.util.Arrays;
publicclassTest{
/**
*@paramstr文本串
*@paramdest模式串
*@paramnext匹配核心数组
*@return
*/
publicstaticintkmp(Stringstr,Stringdest,int[]next){
for(inti=0,j=0;i0&&str.charAt(i)!=dest.charAt(j)){
j=next[j-1];
}
if(str.charAt(i)==dest.charAt(j)){
j++;
}
if(j==dest.length()){
returni-j+1;
}
}
return0;
}
publicstaticint[]kmpnext(Stringdest){
int[]next=newint[dest.length()];
next[0]=0;
for(inti=1,j=0;i0&&dest.charAt(j)!=dest.charAt(i)){
j=next[j-1];
}
if(dest.charAt(i)==dest.charAt(j)){
j++;
}
next[i]=j;
}
returnnext;
}
publicstaticvoidmain(String[]args){
Stringa="ABABAE";
Stringb="ABABABABAEBEABADAEABAEABABAE";
int[]next=kmpnext(a);
System.out.println(Arrays.toString(next));
intres=kmp(b,a,next);
System.out.println(res);
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。
声明：本文内容来源于网络，版权归原作者所有，内容由互联网用户自发贡献自行上传，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任。如果您发现有涉嫌版权的内容，欢迎发送邮件至：czq8825#qq.com（发邮件时，请将#更换为@）进行举报，并提供相关证据，一经查实，本站将立刻删除涉嫌侵权内容。