/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package array;
/**
*
* @author liuyuan
*/
public class KMP_practice {
int m, n, f[];
String str, pat;
public KMP_practice(String str, String pat) {
this.str = str;
this.pat = pat;
m = pat.length();
n = str.length();
f = new int[m];
}
public void Fail() {
f[0] = -1;
int i;
for (int j = 1; j < m; j++) {
i = f[j - 1];
while (pat.charAt(j) != pat.charAt(i + 1) && i != -1) {
i = f[i];
}
if (pat.charAt(j) == pat.charAt(i + 1)) {
f[j] = i + 1;
} else {
f[j] = -1;
}
}
}
public int FastFind() {
Fail();
int p = 0, s = 0;
while (p < m && s < n) {
if (pat.charAt(p) == str.charAt(s)) {
p++;
s++;
} else if (p == 0) {
s++;
} else {
p = f[p - 1] + 1;
}
}
if (p == m) {
return s - m;
} else {
return -1;
}
}
public static void main(String[] args) {
KMP_practice test = new KMP_practice("aaaaaba", "ab");
System.out.println(test.FastFind());
}
}
分享到:
相关推荐
算法 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算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现,因此人们称它为克努特——莫里斯——普拉特操作(简称KMP算法)。KMP算法的关键是利用匹配失败后的信息,尽量减少模式串...
KMP算法
KMP算法详解KMP算法详解KMP算法详解KMP算法详解KMP算法详解
数据结构中KMP算法过程的Flash演示
KMP算法详解KMP算法详解KMP算法详解KMP算法详解
数据结构、kmp算法、代码实现、KMP(char *P,char *T,int *N,int start)
KMP 字符串模式匹配详解 KMP算法是对传统模式匹配算法的较大改进,在传统的模式匹配算法中,当出现主串中的字符与子串中的字符不等时,同时向前回溯了两个指针,一个是主串的指针,一个是子串的指针。而KMP算法的...
\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码\KMP 伪代码
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法是对一般模式匹配算法的改进,由D.E.Knuth与V.R.Pratt和J.H.Morris 同时发现的因此人们称它为克努特-莫里斯-莫拉特操作(简称为KMP算法)。 对于一般的模式匹配算法:分别利用两个指针i和j指示主串S和T中的...
用C++语言实现的KMP算法。经过调试。供广大算法学习者参考。
基于KMP算法的字符串匹配源码, 支持通配符,单匹配和多重匹配。 效率比较高
KMP算法是一种改进的字符串匹配算法,由D.E.Knuth,J.H.Morris和V.R.Pratt提出的,因此人们称它为克努特—莫里斯—普拉特操作(简称KMP算法)。KMP算法的核心是利用匹配失败后的信息,尽量减少模式串与主串的匹配...
kmp算法,数据结构的实验报告,大学实验报告,希望能帮到大家
北大老师写的kmp无回溯算法,数据结构与算法,大家懂得
C++实现kmp字符串匹配算法,算法思想: *KMP算法的思想就是在匹配过程称若发生不匹配的情况 *如果next[j]>=0则目标串的指针i不变将模式串的指针j移动到next[j]的位置继续进行匹配 *若next[j]=-1则将...
此程序配合清华大学出版《数据结构(C语言版)》 P83-84页的KMP算法 win tc调试通过
串的替换,删除,查找 以及KMP算法的具体的实现 c语言 数据结构