最新下载
热门教程
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
用C++与Java代码实现KMP算法实例
时间:2015-10-31 编辑:简简单单 来源:一聚教程网
KMP算法是一种字符串匹配算法,由Knuth,Morris和Pratt同时发现(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数以达到快速匹配的目的。比较流行的做法是实现一个next()函数,函数本身包含了模式串的局部匹配信息。由于next函数理解起来不太容易,本文同样是基于空间换时间的做法,但将采用另一种代码实现,希望可以更方便读者理解!
测试数据
aseeesatba esat
as330kdwejjl_8 jjl_
faw4etoesting tio
aabacb abac
测试结果
4
9
-1
0
(注:若匹配则返回text子串的起始index;否则返回-1)
1.暴力查找的实现一
// 暴力子串查找一式:O(M*N)
private static int search0(String text, String pat) {
int i, j, N = text.length(), M = pat.length();
for (i = 0; i <= N - M; i++) {
for (j = 0; j < M; j++) {
if (text.charAt(i + j) != pat.charAt(j))
break;
}
if (M == j)
return i;
}
return -1;
}
函数传入文本text和模式串pat,其中i和i+j分别标记text子串的首尾。若text存在子串匹配pat,则返回text子串起始index;否则返回-1;时间复杂度:O(M*N)
2.暴力查找实现二
// 暴力子串查找二式:O(M*N)
public static int search(String text, String pat) {
int i, j;
int N = text.length(), M = pat.length();
for (i = 0, j = 0; i < N && j < M; i++) {
if (text.charAt(i) == pat.charAt(j))
j++;
else {
i -= j;
j = 0;
}
}
return (j == M) ? (i - M) : -1;
}
同样的一种暴力查找算法,通过不断的回溯文本串中的“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状态图如下:
对应的代码如下:
//构造dfa[][]
dfa[pat.charAt(0)][0] = 1;
for(int X=0,j=0;j
}
dfa[pat.charAt(j)][j] = j+1;
X = dfa[pat.charAt(j)][X];
}
其中,“X”表示不同的dfa状态,上述代码构造dfa[][]的时间复杂度为:O(N*R);
------------------------------------------------
Java完整代码
package ch05.string.substring;
import java.io.File;
import java.util.Scanner;
public class KMP {
private int R = 255;
private String pat;
private int[][] dfa;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
dfa = new int[R][M];
//构造dfa[][]
dfa[pat.charAt(0)][0] = 1;
for(int X=0,j=0;j
}
dfa[pat.charAt(j)][j] = j+1;
X = dfa[pat.charAt(j)][X];
}
}
public int search(String text){
int i,j;
int N = text.length(),M = pat.length();
for(i=0,j=0;i
}
return j==M?(i-M):-1;
}
public static void main(String[] args) throws Exception {
//从文件读入数据
Scanner input = new Scanner(new File("datain.txt"));
while(input.hasNext()){
String text = input.next();
KMP kmp = new KMP(input.next());
int ans = kmp.search(text);
//输出答案
System.out.println(ans);
}
}
}
------------------------------------------------
C/C++完整代码
#include
#include
#include
#include
using namespace std;
const int maxn=1e4+10;
const int R=256;
int dfa[R][maxn];
string text,pat;
void init(){
int M=pat.length();
dfa[pat[0]][0] = 1;
for(int X=0,j=1;j
for(int c=0;c
}
/**匹配到,继续往右走*/
dfa[pat[j]][j] = j+1;
X = dfa[pat[j]][X];
}
}
int search1(){
init();
int i,j,N = text.length(),M = pat.length();
for(i=0,j=0;i
}
return j==M?(i-M):-1;
}
int main(){
freopen("datain.txt","r",stdin);
while(cin>>text>>pat){
cout<
return 0;
}
相关文章
- C++ MD5的源码实例详解 01-19
- 实例分析c++拷贝初始化与直接初始化的底层区别 10-31
- c/c++扩展python实例学习教程 08-08
- C++中 set,multiset,map,multimap 关联容器实例教程 08-04
- 超详细的C++指针介绍及实例教程 04-17
- 深入学习 C++ 临时对象的实例教程 03-14