- 浏览: 28413 次
- 性别:
- 来自: 杭州
文章分类
最新评论
package zl.character.compare;
/**
* 字符串匹配 kmp算法
* KMP算法实质:利用已经遍历得到的匹配信息来辅助后面的匹配过程
* @author bo
*
*/
public class Kmp {
/**
* next[j] = k 代表索引5的元素直接k-1个元素和开头k-1个元素相匹配(next数组表示 当pj元素失配的时候 需要把模式串向右移动到什么位置)
* 即p0...p(k-1) 和 p(j-k)...p(j-1) 相等
* 所以 0 < k < j
* @param list
* @return
*/
private int[] getNext(char[] list) {
int len = list.length;
int[] next = new int[len+1];
next[0] = -1;
int i = 0;
int j = -1; //代表k
System.out.println("netx[0]=-1");
while(i < (len - 1)) {
if(j == -1 || list[i] == list[j]) {
i++;
j++;
/*
* 当pk 和 pj 相等的时候 p(j+1) 如果不相等 需要移动到p(k+1)上
* 但是,如果p(j+1) = p(k+1) 即使移动也是陪同同一个字符 所以把p(j+1)不匹配问题转移到p(k+1)的元素上
*/
if(list[j] == list[i])
next[i] = next[j];
else
next[i] = j;
System.out.println("next["+i+"]=" + next[i] );
} else
j = next[j];
}
return next;
}
public void kmp(char[] s , char[] m , int[] t) {
int len = s.length;
int number = m.length;
int j = 0;
int i = 0;
while(i < len && j < number) {
if(s[i] == m[j]) {
i++;
j++;
} else {
j = t[j];
if(j == -1) {
j = 0;
i++;
}
}
}
if(j == number) {
System.out.println("匹配位置:" + i);
}
}
/**
* @param args
*/
public static void main(String[] args) {
Kmp kmp = new Kmp();
char[] m = "abababb".toCharArray();
char[] s = "abababababb".toCharArray();
int[] next = kmp.getNext(m);
kmp.kmp(s,m,next);
}
}
/**
* 字符串匹配 kmp算法
* KMP算法实质:利用已经遍历得到的匹配信息来辅助后面的匹配过程
* @author bo
*
*/
public class Kmp {
/**
* next[j] = k 代表索引5的元素直接k-1个元素和开头k-1个元素相匹配(next数组表示 当pj元素失配的时候 需要把模式串向右移动到什么位置)
* 即p0...p(k-1) 和 p(j-k)...p(j-1) 相等
* 所以 0 < k < j
* @param list
* @return
*/
private int[] getNext(char[] list) {
int len = list.length;
int[] next = new int[len+1];
next[0] = -1;
int i = 0;
int j = -1; //代表k
System.out.println("netx[0]=-1");
while(i < (len - 1)) {
if(j == -1 || list[i] == list[j]) {
i++;
j++;
/*
* 当pk 和 pj 相等的时候 p(j+1) 如果不相等 需要移动到p(k+1)上
* 但是,如果p(j+1) = p(k+1) 即使移动也是陪同同一个字符 所以把p(j+1)不匹配问题转移到p(k+1)的元素上
*/
if(list[j] == list[i])
next[i] = next[j];
else
next[i] = j;
System.out.println("next["+i+"]=" + next[i] );
} else
j = next[j];
}
return next;
}
public void kmp(char[] s , char[] m , int[] t) {
int len = s.length;
int number = m.length;
int j = 0;
int i = 0;
while(i < len && j < number) {
if(s[i] == m[j]) {
i++;
j++;
} else {
j = t[j];
if(j == -1) {
j = 0;
i++;
}
}
}
if(j == number) {
System.out.println("匹配位置:" + i);
}
}
/**
* @param args
*/
public static void main(String[] args) {
Kmp kmp = new Kmp();
char[] m = "abababb".toCharArray();
char[] s = "abababababb".toCharArray();
int[] next = kmp.getNext(m);
kmp.kmp(s,m,next);
}
}
发表评论
-
NIO 简单实现的服务端和客户端通信
2015-06-29 11:35 652服务端代码如下: import java.io.IOExcep ... -
aaaaaaaaaaaa
2014-08-30 09:01 0111111111111111 -
struts2与checkbox的关系
2014-03-25 15:35 581Struts2 框架对checkbox的处理 1、 对于htm ... -
doc命令之关机管理
2014-03-21 09:26 652@echo off set /p p=是否关机(1:关机 2: ... -
金字塔最短路径
2014-03-18 10:02 544class Triangle { private int[] ... -
汉诺塔递归算法
2014-03-15 10:49 527class Hanio { private int st ... -
回溯算法之八皇后
2014-03-13 13:27 561public class EightQueens { ... -
xml的基本学习
2014-03-04 15:17 7981、 XML的概念 允许开发 ... -
软件生命三大测试的概念和区别
2014-02-17 22:01 0根据不同的测试阶段,测试可以分为单元测试、集成测试、系统测试和 ... -
Session处理同账号管理
2013-10-22 17:19 721首先使用HttpSessionAttributeListene ... -
线程概念
2013-03-20 21:06 0线程对可共享的、可改变的状态变量进行访问,需要实现协同,否则数 ... -
parseInt惹的祸
2013-03-04 17:57 755今天项目在实施的过程中,出现了让我懊恼的事情: 卡的金额读不出 ... -
Unable to retrieve metadata for procedure
2013-03-01 13:51 3838第一次用jdbc调用mysql存储过程的过程中犯了一个严重的错 ... -
JDK动态代理和CGLIB动态代理的学习
2012-10-08 17:25 0JDK动态代理是基于java.lang.reflect.Pro ... -
log4j输出spring框架的信息
2012-10-08 17:00 0log4j.logger.org.springframewor ... -
ReadWriteLock多线程下操作
2012-09-06 17:45 931ReadWriteLock是实现多线程环境下同步的一种方式。与 ... -
WIN7 BCompare 启动应用程序发生错误
2012-08-24 11:26 1027WIN7下寻找: 把C:\用户\[用户名]\AppData\S ... -
ant
2012-08-24 11:15 0当使用-jar执行可执行Jar包时,JVM将Jar包所在目录设 ... -
java 学习
2012-08-14 21:18 577使用final声明的类不能有子类 使用final声明的方法不能 ... -
spring框架后处理器的学习
2012-07-27 09:22 651spring框架对容器管理bean和容器本身提供了额外增强功能 ...
相关推荐
KMP算法
算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP算法 KMP
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
kmp算法,数据结构的实验报告,大学实验报告,希望能帮到大家
数据结构中KMP算法过程的Flash演示
kmp算法 KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...
DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法DS串应用--KMP算法
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的...
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
KMP算法实现 KMP算法实现 KMP算法实现 KMP算法实现
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
kmp算法的原理以及kmp算法的源代码
使用KMP算法实现模式匹配,包括next数组的求解,kmp算法的实现。关键代码有详细注释。
KMP算法的实现, 这程序代码是基于KMP算法来实现的,虽然很简单,但是可能也会对你有帮助的
利用KMP算法进行子串的快速查找,能够达到较高的速率