用Java实现KMP算法,并与String.indexOf方法做比较。
public static int kmp1(String pattern, String src){
int srcLength = src.length() ;
int patternLength = pattern.length() ;
int index = -1 ;
int count = 0 ;
for(int i = 0 ; i < srcLength - 1 ;){
count = 0 ;
for(int j = 0 ; (j < patternLength ) && (i < srcLength) ; j++){
if(src.charAt(i) == pattern.charAt(j)){
count++ ;
i++ ;
}else{
break ;
}
}
if(count == patternLength){
return i - count ;
}
if(count == 0){
i++ ;
}
}
return index ;
}
测试程序如下:
public static void main(String[] args){
String src = "1234567890abcdefghijk" ;
String pattern = "abcd" ;
long beginTime = System.nanoTime() ;
int index = kmp1(pattern, src) ;
System.out.println("My KMP : index = " + index + " and time = " + (System.nanoTime() - beginTime) + "ns");
beginTime = System.nanoTime() ;
index = src.indexOf(pattern) ;
System.out.println("String.indexOf : index = " + index + " and time = " + (System.nanoTime() - beginTime) + "ns");
}
结果很悲剧,输出如下
My KMP : index = 10 and time = 58012 ns
String.indexOf : index = 10 and time = 9895 ns
对代码进行修改,发现方法kmp1在内层循环中对条件判断的使用有些费操作,遂修改如下:
public static int kmp2(String pattern, String src){
int srcLength = src.length() ;
int patternLength = pattern.length() ;
int index = -1 ;
int count = 0 ;
for(int i = 0 ; i < srcLength - 1 ;){
count = 0 ;
for(int j = 0 ; (j < patternLength ) && (i < srcLength) && (src.charAt(i) == pattern.charAt(j)); j++,i++,count++) ;
if(count == patternLength){
return i - count ;
}
if(count == 0){
i++ ;
}
}
return index ;
}
执行后发现没什么效果,输出如下:
My KMP : index = 10 and time = 57070 ns
String.indexOf : index = 10 and time = 9961 ns
再将字符串改为对字符数组的操作
public static int kmp3(char[] patternArray , char[] srcArray){
int index = -1 ;
int count = 0 ;
for(int i = 0 ; i < srcArray.length - 1 ;){
count = 0 ;
for(int j = 0 ; (j < patternArray.length ) && (i < srcArray.length) && (srcArray[i] == patternArray[j]); j++,i++,count++) ;
if(count == patternArray.length){
return i - count ;
}
if(count == 0){
i++ ;
}
}
return index ;
}
效果依然不好:
My KMP : index = 10 and time = 55805 ns
String.indexOf : index = 10 and time = 10277 ns
各位看官,给点提醒吧,还可以从哪里优化吗?还是说,我写的KMP本身就有问题?
分享到:
相关推荐
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构
数据结构课程设计,用KMP算法实现的文本检索,检索本地文件,使用MFC,可视化界面
KMP算法实现的C++代码,KMP算法实现的C++代码,KMP算法实现的C++代码
简单的kmp算法实现,代码结构十分清晰,适合初学者理解kmp算法
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
kmp算法 kmp算法_基于Python+kmp算法实现模糊文本字符串匹配
编程求出子串(模式串)的next值,利用kmp算法实现子串与多个主串的匹配,针对同一子串next值只计算一次。
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
KMP算法实现,VS2005平台语言C++,完全可以实现,我在主程序里加了一个for循环,为了测试时间,各位下了以后可以自行修改
用kmp算法实现在一个网页内网址的提取,自己实现kmp算法部分。
BF算法和Kmp算法实现串匹配完整代码。
KMP算法是数据结构中解决字符串匹配问题的经典算法,文件中包括算法实现和详细分析,下载可直接运行调试,可供数据结构与算法课程的学习
acm算法模板之kmp模板,对关键代码做了注释,帮助小白理解
高效的字符串匹配算法 KMP 实现,采用C语言实现
具体实现上,KMP算法使用一个next()函数,该函数包含模式串的局部匹配信息。在匹配失败时,next()函数用来确定模式串的最左可能有效匹配位置,而非简单地将模式串重新从左向右扫描。这样大大减少了不必要的匹配次数...
使用KMP算法实现一个模式匹配.doc
很多教材只是介绍了KMP的思想却没有实现,而他的实现对初学者又有一定难度,故共享该资源
模式匹配中的KMP算法的c语言实现及简单的应用介绍!