经典KMP算法C++与Java实现代码

来源:互联网 时间:1970-01-01

前言:

KMP算法是一种 字符串匹配 算法,由Knuth,Morris和Pratt同时发现(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。比较流行的做法是实现一个next()函数,函数本身包含了模式串的局部匹配信息。由于next函数理解起来不太容易,本文同样是基于空间换时间的做法,但将采用另一种代码实现,希望可以更方便读者理解!

测试数据 aseeesatba esatas330kdwejjl_8 jjl_faw4etoesting tioaabacb abac 测试结果 49-10

(注:若匹配则返回text子串的起始index;否则返回-1)

1.暴力查找的实现一 1 // 暴力子串查找一式:O(M*N) 2 private static int search0(String text, String pat) { 3 int i, j, N = text.length(), M = pat.length(); 4 for (i = 0; i <= N - M; i++) { 5 for (j = 0; j < M; j++) { 6 if (text.charAt(i + j) != pat.charAt(j)) 7 break; 8 } 9 if (M == j)10 return i;11 }12 return -1;13 }

函数传入文本text和模式串pat,其中i和i+j分别标记text子串的首尾。若text存在子串匹配pat,则返回text子串起始index;否则返回-1;时间复杂度:O(M*N)

2.暴力查找实现二 1 // 暴力子串查找二式:O(M*N) 2 public static int search(String text, String pat) { 3 int i, j; 4 int N = text.length(), M = pat.length(); 5 for (i = 0, j = 0; i < N && j < M; i++) { 6 if (text.charAt(i) == pat.charAt(j)) 7 j++; 8 else { 9 i -= j;10 j = 0;11 }12 }13 return (j == M) ? (i - M) : -1;14 }

同样的一种暴力查找算法,通过不断的回溯文本串中的“i”进行判断。若text存在子串匹配pat,则返回text子串起始index;否则返回-1;时间复杂度:O(M*N)

3.KMP算法(空间换时间)

为了优化算法时间复杂度,我们尝试进行一些信息存储,引入了额外的空间存储 dfa[][]。

从上述第二种暴力查找算法中,我们可以得到启发。即,通过记录“j”保证“i”只能往右移动,无需往左回退。其中,dfa[i][j]

表示文本串中当前字符‘charAt(i)’时,下个文本字符'charAt(i+1)'应该与模式串匹配的位置(0~j)。

这里我们引入有穷自动机DFA对dfa[][]进行数值的初始化。以模式串“aabacb”为例,匹配pat的DFA状态图如下:

对应的代码如下:

1 //构造dfa[][]2 dfa[pat.charAt(0)][0] = 1;3 for(int X=0,j=0;j<M;j++){4 for(int c=0;c<R;c++){5 dfa[c][j] = dfa[c][X];6 }7 dfa[pat.charAt(j)][j] = j+1;8 X = dfa[pat.charAt(j)][X];9 }

其中,“X”表示不同的dfa状态,上述代码构造dfa[][]的时间复杂度为:O(N*R);

------------------------------------------------

Java完整代码

1 package ch05.string.substring; 2 3 import java.io.File; 4 import java.util.Scanner; 5 6 public class KMP { 7 8 private int R = 255; 9 private String pat;10 private int[][] dfa;11 12 public KMP(String pat) {13 this.pat = pat;14 int M = pat.length();15 dfa = new int[R][M];16 17 //构造dfa[][]18 dfa[pat.charAt(0)][0] = 1;19 for(int X=0,j=0;j<M;j++){20 for(int c=0;c<R;c++){21 dfa[c][j] = dfa[c][X];22 }23 dfa[pat.charAt(j)][j] = j+1;24 X = dfa[pat.charAt(j)][X];25 }26 27 }28 29 public int search(String text){30 int i,j;31 int N = text.length(),M = pat.length();32 for(i=0,j=0;i<N && j<M; i++){33 j = dfa[text.charAt(i)][j];34 }35 return j==M?(i-M):-1;36 }37 38 public static void main(String[] args) throws Exception {39 //从文件读入数据40 Scanner input = new Scanner(new File("datain.txt"));41 while(input.hasNext()){42 String text = input.next();43 KMP kmp = new KMP(input.next());44 int ans = kmp.search(text);45 //输出答案46 System.out.println(ans);47 }48 }49 }

------------------------------------------------

C/C++完整代码

1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<string> 5 using namespace std; 6 const int maxn=1e4+10; 7 const int R=256; 8 int dfa[R][maxn]; 9 10 string text,pat;11 void init(){12 int M=pat.length();13 dfa[pat[0]][0] = 1;14 for(int X=0,j=1;j<M;j++){15 /**直接从dfa[][X]复制到dfa[][j]*/16 for(int c=0;c<R;c++){17 dfa[c][j] = dfa[c][X];18 }19 /**匹配到,继续往右走*/20 dfa[pat[j]][j] = j+1;21 X = dfa[pat[j]][X];22 }23 24 }25 int search1(){26 init();27 int i,j,N = text.length(),M = pat.length();28 for(i=0,j=0;i<N && j<M;i++){29 j = dfa[text[i]][j];30 }31 return j==M?(i-M):-1;32 }33 int main(){34 freopen("datain.txt","r",stdin);35 while(cin>>text>>pat){36 cout<<search1()<<endl;37 }38 return 0;39 }

Reference:

【1】Algorithms(4th) -谢路云

【2】http://baike.baidu.com/link?url=_WLufLz1lw2e4eMgU6DI8IblUkp838Qf595Nqxfg2JN3aqNED2FFe3U6J9yPmUv_zKfFqAAQJid7Gzho3ork8K



相关阅读:
Top