`
- 浏览:
459731 次
- 性别:
- 来自:
北京
-
- public class KMP {
-
-
private String text;
-
private String pattern;
-
- KMP() {
-
- }
-
- KMP(String text, String pattern) {
-
this.text = text;
-
this.pattern = pattern;
- }
-
-
public void setText(String text) {
-
this.text = text;
- }
-
-
public void setPattern(String pattern) {
-
this.pattern = pattern;
- }
-
-
public void KMPMatcher() {
-
int n = text.length();
-
int m = pattern.length();
-
-
int prefix[] = computePrefix();
-
int q = 0;
-
-
int count = 0;
-
for(int i = 0; i < n; i++) {
-
-
while(q > 0 && pattern.charAt(q)!= text.charAt(i)) {
-
q = prefix[q -1];
- }
-
-
if(pattern.charAt(q) == text.charAt(i))
- q++;
-
-
if(q == m) {
-
System.out.println("Pattern occurs with shift " + ++count + "times");
-
q = prefix[q - 1];
- }
- }
-
-
if(count == 0) {
-
System.out.println("There is no matcher!");
- }
- }
-
-
private int[] computePrefix() {
-
int length = pattern.length();
-
int[] prefix = new int[length];
-
-
prefix[0] = 0;
-
-
int k = 0;
-
for(int i = 1; i < length; i++) {
-
while(k > 0 && pattern.charAt(k) != pattern.charAt(i)) {
-
k = prefix[k -1];
- }
-
if(pattern.charAt(k) == pattern.charAt(i))
- k++;
- prefix[i] = k;
- }
-
-
return prefix;
- }
-
-
public static void main(String[] args) {
-
- KMP kmp;
-
-
if(args.length == 2) {
-
kmp = new KMP(args[0] , args[1]);
- }
-
else {
-
kmp = new KMP();
-
kmp.setText("ababacabacbababababacabcbabababaca");
-
kmp.setPattern("ababaca");
- }
-
- kmp.KMPMatcher();
-
- }
分享到:
Global site tag (gtag.js) - Google Analytics
相关推荐
KMP算法是通过分析子串,预先计算每个位置发生不匹配的时候,所需GOTO的下一个比较位置,整理出来一个next数组,然后在上面的算法中使用。
KMP算法实现,用Java语言实现的KMP字符串匹配算法
kMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法JavakMP算法Java...
欢迎讨论
带有简单示例,亲测可用!!! 函数组成: public static void main(String[] args) private int search(String str, String pat) public static int[] generateNext(String dest)
这是个比较难理解的算法,虽然代码就那么几行,但真正理解清楚还是要会时间的。
java实现的kmp算法,参照原论文实现的,希望能有用
用java写的KMP算法,这是个描述KMP算法的java类,里面包含了主函数的实例
JAVA实现KMP算法,使用java语言实现的kmp算法
KMP算法的JAVA实现
kmp算法 kmp算法的Java实现
kmp算法 kmp算法_基于Java实现的kmp算法
KMP算法的Java实现 public class KMP { public static int[] next; static void GetNext(String p,int next[]) { int pLen = p.length(); next[0] = -1;
* Java实现KMP算法 * * 思想:每当一趟匹配过程中出现字符比较不等,不需要回溯i指针, * 而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远 * 的一段距离后,继续进行比较。 * * 时间复杂度O...
java实现KMP算法,代码非常简单,容易理解。
kmp算法的java代码
kmp算法
KMP算法的java实现,KMP详细解说请移步:https://blog.csdn.net/Michaelia_hu/article/details/100888201
KMP算法
数据结构C++实现KMP算法class kmp 怎么得到nextval数组怎么比较字符串