如何通过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(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。
热门推荐
1 训练狗狗搜寻
2 如何训练狗狗装死
3 狗狗训练书
6 怎么训练狗狗拜年
8 狗狗训练游戏
10 狗狗嗅觉训练
11 怎么训练狗狗在笼子里不叫
12 怎么训练狗狗站立走路
13 怎么训练狗狗在马桶上
14 狗狗尿尿怎么训练
15 训练狗狗用品
16 泰迪狗狗的训练方法大小便
17 训练狗狗可以打吗
18 王曼丽的狗狗训练