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

前言：

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

测试数据

aseeesatba   esat
as330kdwejjl_8   jjl_
faw4etoesting tio
aabacb abac

测试结果

（注：若匹配则返回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