package com.tobaidu.algorithm.kmp;
public class KMP {
static int[] P;
/**
* 对子串加以预处理,从而找到匹配失败时子串回退的位置
*
* @param B
* ,待查找子串的char数组
* @return
*/
public static int[] preProcess(char[] B) {
int size = B.length;
int[] P = new int[size];
P[0] = 0;
int j = 0;
for (int i = 1; i < size; i++) {
while (j > 0 && B[j] != B[i]) {
j = P[j];
}
if (B[j] == B[i]) {
j++;
}
P[i] = j;
}
return P;
}
/**
* KMP实现
*
* @param parStr
* @param subStr
* @return
*/
public static void kmp(String parStr, String subStr) {
int subSize = subStr.length();
int parSize = parStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
int j = 0;
int k = 0;
for (int i = 0; i < parSize; i++) {
while (j > 0 && B[j] != A[i]) {
j = P[j - 1];
}
if (B[j] == A[i]) {
j++;
}
if (j == subSize) {
j = P[j - 1];
k++;
}
}
}
public static void main(String[] args) {
// 回退位置数组为P[0, 0, 0, 0, 0, 0]
kmp("abcdeg, abcdeh, abcdef!这个会匹配1次", "abcdef");
// 回退位置数组为P[0, 0, 1, 2, 3, 4]
kmp("Test ititi ititit! Test ititit!这个会匹配2次", "ititit");
}
}
package com.tobaidu.algorithm.kmp;
public class SubStrFind {
/**
* 字符串查找(枚举方法)
*
* @param parStr
* @param subStr
* @return
*/
public static void strFind(String parStr, String subStr) {
int parSize = parStr.length();
int subSize = subStr.length();
char[] B = subStr.toCharArray();
char[] A = parStr.toCharArray();
boolean flag = true;
int times = 0;
int j = 0;
int k = 0;// k记录父串匹配正确的位置或者匹配不正确的回退位置
// i记录父串的当前比较字符的位置
for (int i = 0; i < parSize; i++) {
if (B[j] == A[i]) {
j++;
// 第一次时记录父串回退位置
if (flag) {
k = i;
flag = false;
}
} else {
// 不匹配时回退位置重置,比较继续进行
i = ++k;
j = 0;
flag = true;
}
if (j == subSize) {
j = 0;// 匹配时只需把子串回退位置重置,比较继续进行
flag = true;
times++;
}
}
}
}
package com.tobaidu.algorithm.kmp;
public class TimeConsumer {
private static int times = 1000000;
public static void test(String parStr, String subStr) {
long start = 0;
long end = 0;
System.out.println("父串: " + parStr);
System.out.println("子串: " + subStr);
start = System.currentTimeMillis();
KMP.P = KMP.preProcess(subStr.toCharArray());
for (int i = 0; i < times; i++) {
KMP.kmp(parStr, subStr);
}
end = System.currentTimeMillis();
System.out.println("Time for KMP: " + (end - start));
start = System.currentTimeMillis();
for (int i = 0; i < times; i++) {
SubStrFind.strFind(parStr, subStr);
}
end = System.currentTimeMillis();
System.out.println("Time for Enumeration: " + (end - start));
System.out.println("-------------------------------------");
}
public static void main(String[] args) {
test("abcdeg, abcdeh, abcdef!这个会匹配1次", "abcdef");
test("Test ititi ititititd! Test ititititd!这个会匹配2次", "ititititd");
}
}
分享到:
相关推荐
Knuth-Morris-Pratt algorithm
KMPAlgorithm.c
字符串匹配是计算机的基本任务之一。 举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”...许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。
这是一个关于字符串匹配的kmp算法,程序简单精炼,可以借鉴一下
kmp算法kmp-algorithm-master.zip
KMP算法 字符串匹配算法 The KMP algorithm string matching algorithm
poj 上的几道kmp 题的解题报告 sourse code of kmp algorithm
KMP algorithm for matching string problem
kmp算法,kmp-algorithm-master (1).zip
parrallel computing string with kmp algorithm
The classical KMP algorithm for string matching (the target string can be modified in the main function, if any match is found, the matching position would be returned)
...The number of questions is increasing recently. Here is the classification of all `468` questions. ...I'll keep updating for full summary and better solutions....|-----|---------------- | --------------- |...
KMP for string matching
KMP(Knuth-Morris-Pratt)算法是一种改进的字符串匹配算法,用于在一个文本字符串(T)中查找一个词(W)的出现位置。KMP算法的核心在于当字符串匹配发生不一致时,能知道已经部分匹配这个有效信息,利用这个信息...
KMP算法的一个经典题题解,
HDU-1711 Number Sequence(KMP算法)For each test case, you should output one line wh
克努斯-莫里斯-普拉特算法,KMP算法(Knuth–Morris–Pratt algorithm) 一种字符串查找算法。在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来...
KMP算法(Knuth-Morris-Pratt Algorithm)是一种改进的字符串匹配算法,由D.E.Knuth、J.H.Morris和V.R.Pratt提出。该算法的核心思想是利用匹配失败后的信息,尽量减少模式串与主串的匹配次数,以达到快速匹配的目的...
StringMatch:这是Randomized Algorithm类的最终项目。 基本比较了朴素算法,Rabin-Karp算法和KMP算法的性能