Java怎么实现KMP算法

2024-10-28 技术教程

本篇内容主要讲解“Java怎么实现KMP算法”，感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷，实用性强。下面就让小编来带大家学习“Java怎么实现KMP算法”吧!

KMP 算法

KMP (Knuth-Morris-Pratt), 是一种改进的字符串匹配算法. KMP 算法解决了暴力匹配需要高频回退的问题, KMP 算法在匹配上若干字符后, 字符串位置不需要回退, 从而大大提高效率. 如图:

举个例子 (字符串 “abcabcdef” 匹配字符串 “abcdef”):

次数暴力匹配KMP 算法说明1abcabcdef abcdefabcabcdef abcdefa 和 a 匹配2abcabcdef abcdefabcabcdef abcdefab 和 ab 匹配3abcabcdef abcdefabcabcdef abcdefabc 和 abc 匹配4abcabcdef abcdefabcabcdef abcdefabca 和 abcd 不匹配, 回退. 暴力匹配回退到索引 1, 即 “b”, KMP 算法索引跳置 3, 即 “a”5abcabcdef abcdefabcabcdef abcdef暴力匹配 b 和 a 不匹配, 后移. KMP 算法 a 和 a 匹配6abcabcdef abcdefabcabcdef abcdef暴力匹配 c 和 a 不匹配, 后移. KMP 算法 ab 和 ab 匹配7abcabcdef abcdefabcabcdef abcdef暴力匹配 a 和 a 匹配. KMP 算法 abc 和 abc 匹配8abcabcdef abcdefabcabcdef abcdef暴力匹配 ab 和 ab 匹配. KMP 算法 abcd 和 abcd 匹配9abcabcdef abcdefabcabcdef abcdef暴力匹配 abc 和 abc 匹配. KMP 算法 abcde 和 abcde 匹配10abcabcdef abcdefabcabcdef abcdef暴力匹配 abcd 和 abcd 匹配. KMP 算法 abcdef 和 abcdef 匹配 , 匹配完成11abcabcdef abcdefabcabcdef abcdef暴力匹配 abcde 和 abcde 匹配. KMP 算法匹配完成12abcabcdef abcdefabcabcdef abcdef暴力匹配 abcd 和 abcd 匹配, 匹配完成. KMP 算法匹配完成部分匹配表

部分匹配表 (Partial Match Table) 指的是 “前缀” 和 “后缀” 的最长共有元素的长度.

举个例子, 字符串 “ABCDABD” 的前缀与后缀:

字符串前缀后缀共同部分值ANaNNaNNaN0ABABNaN0ABCA, ABC, BCNaN0ABCDA, AB, ABCD, CD, BCDNaN0ABCDAA, AB, ABC, ABCDA, DA, CDA, BCDAA1ABCDABA, AB, ABC, ABCD, ABCDAB, AB, DAB, CDAB, BCDABAB2ABCDABA, AB, ABC, ABCD, ABCDA, ABCDABD, BD, ABD, DABD, CDABD, BCDABDNaN0KMP 算法实现

重点:

KMP 算法中移动的位数 = 已匹配的字符数 - 对应的部分匹配值

importjava.util.Arrays;publicclassKMPMatch{publicstaticintMatch(Stringstr1,Stringstr2,int[]next){//初始化索引inti=0;intj=0;for(;i<str1.length();i++){if(j>0&&str1.charAt(i)!=str2.charAt(j)){//不匹配,回退i=i-next[j-1];j=0;}//匹配if(str1.charAt(i)==str2.charAt(j)){j++;}//返回索引if(j==str2.length()){returni-j+1;}}return-1;}//部分匹配publicstaticint[]getNext(Strings){//定义数组intnext[]=newint[s.length()];//初始化i,jinti=0;intj=-1;next[0]=-1;//遍历while(i<s.length()-1){if(j==-1||s.charAt(i)==s.charAt(j)){//匹配成功next[i]=j+1;i++;j++;}else{//一旦不匹配成功j回退到-1j=-1;}}returnnext;}publicstaticvoidmain(String[]args){//字符串1Stringstr1="BBCABCDABABCDABD";//字符串2Stringstr2="ABCDABD";//匹配表int[]next=getNext(str2);System.out.println(Arrays.toString(next));//KMP算法intresult=Match(str1,str2,next);System.out.println(result);}}

输出结果: