package sunfa.kmp;
/**
* 朴素字符串匹配算法
*/
public class SimpleKMP {
public static void main(String[] args) {
int index = simpleKmp("12444abababab", "444ababab");
System.out.println(index);
}
/**
* 朴素字符串匹配算法的一个特点是主字符串指针要回溯
* 性能o((n-m+1)m)
* @param src
* @param dect
* @return
*/
private static int simpleKmp(String src, String dect) {
if (dect.length() > src.length())
return -1;
char[] srcArr = src.toCharArray();
char[] dectArr = dect.toCharArray();
for (int i = 0; i < srcArr.length; i++)
if ((i + dect.length()) <= srcArr.length
&& comp(srcArr, dectArr, i, i + dect.length()))
return i;
return -1;
}
private static boolean comp(char[] srcArr, char[] dectArr, int a0, int a1) {
int j = 0;
for (int i = a0; i < a1; i++)
if (srcArr[i] != dectArr[j++])
return false;
return true;
}
}
package sunfa.kmp;
import java.util.Arrays;
/**
* 这个算法比较靠谱,而且看的懂 KMP算法分2步:
* <p>
* ①根据子字符串得到next数组
* <p>
* ②子串与主串进行朴素比较,但是匹配不上的时候就查找next数组。
* 以前在这个时候是i回溯并且j=0,kmp算法是i不动并且j回溯(根据next数组进行回缩,
* 找到那个能够匹配上的地方。它怎么知道哪个地方能够匹配的上呢,看看next数组的实现就清楚了。)
*
* next数组的实现:对子串进行迭代,每次取p.substring(0, i)个字符,然后把该字符劈成两半并且比较左半边和右半边是否相等,
* 如果相等则将两半处的索引n加到next数组中去
* <p>
*
*
* /**
* kmp算法 一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此称之为KMP算法。此算法可以在O
* (n+m
* )的时间数量级上完成串的模式匹配操作,其基本思想是:每当匹配过程中出现字符串比较不等时,不需回溯指针,而是利用已经得到的“部分匹配”结果将模式向右“
* 滑动”尽可能远的一段距离,继续进行比较。 参考http://www.iteye.com/topic/501047
*
* KMP算法的思路:
* http://iaiai.iteye.com/blog/1140796
*
*/
*/
public class KMP {
String s; // 主字符串
String p; // 匹配字符串
int[] next; // 匹配字符串的next数组
int times; // 记录匹配的次数
int index; // 记录查找到的位置
/**
* 构造函数,初始化各个成员变量
*
* @param s
* @param p
*/
KMP(String s, String p) {
this.s = s;
this.p = p;
this.next = new int[p.length()];
for (int i = 0; i < p.length(); i++) {
if (i == 0) {
this.next[i] = -1;
} else if (i == 1) {
this.next[i] = 0;
} else {
// 对某个位置之前的字符串考察其开始部分和结尾部分是否相同
this.next[i] = next(p.substring(0, i));
}
}
this.times = 0;
this.index = -1;
}
/**
* 返回子字符串,开始部分和结尾部分相同的情况下的开始部分的下一个位置,即next值
*
* @param p
* @return
*/
private int next(String p) {
int length = p.length() / 2;
while (length > 0) {
if (p.substring(0, length).compareTo(
p.substring((p.length() - length), p.length())) == 0) {
System.out.println(p + "<" + p.substring(0, length) + "="
+ p.substring((p.length() - length), p.length()));
return length;
}
length--;
}
return length;
}
/**
* 对主字符串进行比较,碰到不匹配,查询next数组;如果新元素和当前不匹配元素相同,则继续next
*
* @return
*/
boolean match() {
int i = 0;// 主串索引
int j = 0;// 子串索引
int index = -1; // index记录匹配的位置
while (i < this.s.length() && j < this.p.length()) {
if (this.s.charAt(i) == this.p.charAt(j)) {// 1、按照朴素模式进行匹配
if (j == 0) {
index = i;
}
i++;
j++;
} else {
// 一直寻找next,直到和当前元素不相等的元素,将其下标赋值给j
int newj = this.next[j];// 2、当匹配不上了的时候i不用回溯,只需要根据j的索引去查找next数组
System.out.print("debug[");
while ((newj != -1)
&& (this.p.charAt(newj) == this.p.charAt(j))) {
// newj回溯
newj = this.next[newj];
System.out.print("newj:" + newj + ",i:" + i + ",j:" + j
+ ",v:" + this.p.charAt(j) + ",next:"
+ Arrays.toString(next) + ",p:" + p);
}
System.out.println("]");
j = newj;
if (j == -1) {
i++;// 主串索引++
j = 0;// 子串索引重置
} else {
index = i - j;
}
}
this.times++;
}
if (j == this.p.length()) {
this.index = index;
return true;
} else {
return false;
}
}
public static void main(String[] args) {
String s = "1ababcababd1ababcababc_def";
String p = "ababcababc";
KMP m = new KMP(s, p);
// 顺便打印next数组;
for (int i = 0; i < m.next.length; i++) {
System.out.print(m.next[i] + ",");
}
System.out.println();
if (m.match()) {
System.out.println("match");
System.out.println("match times: " + m.times);
int index = m.index;
System.out.println(index);
} else {
System.out.println("not match");
}
}
}
分享到:
相关推荐
KMP字符串匹配算法,一种快速模式匹配算法
字符串的模式匹配算法——KMP的C++实现。
KMP字符匹配算法,KMP算法,字符匹配算法
字符串匹配 KMP算法
运用C++实现中文字符的KMP匹配算法,实现关键字搜索
带通配符的字符串匹配算法,带通配符的字符串匹配算法
KMP字符串模式匹配算法ppt,KMP算法是很精妙的算法,同时比较难懂。KMP字符串模式匹配算法ppt
最经典的KMP算法,VC工程下的源码,便于初学者学习,理解该算法
代码封装了字符串的kmp模式匹配算法。kmp是一种非常快速的字符串匹配算法,效率比普通匹配算法高很多
一种改进的字符串匹配算法,由D.E.Knuth与V.R.Pratt和J.H.Morris同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串与主串的...
KMP字符串模式匹配算法,内是ppt讲解,比较通俗易懂了。。
很多数据结构的教材都提到字符串匹配的KMP算法,但鲜有阐述此算法原理者。本文试图对此做一个直观易懂的解释。
里面含有传统字符串匹配以及kmp算法匹配,包含kmp 导出的Archive file 文件修改jdk可以直接运行
这是字符串匹配算法中很著名的KMP算法,此文件仅供大家参考,具体是否能调通,本人还没有试过
关于KMP_字符串模式匹配算法的教学课件,详细讲解了Kmp 的原理与不足和改进
我自己用C语言写的,用了KMP算法,实现了从文件中查找字符的功能。
KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的基本思路是在不回溯主串的...
克努斯-莫里斯-普拉特算法,KMP算法(Knuth–Morris–Pratt algorithm) 一种字符串查找算法。在一个“主文本字符串” S 内查找一个“词” W 的出现,通过观察发现,在不匹配发生的时候这个词自身包含足够的信息来...
程序开发过程中的字符串匹配算法很多,这里出了算法的程序源代码,包括C#,C++, Delphi代码,大家直接下载就可以拷贝到自己程序中使用。