文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > KMP算法代码实现(java版)
侵权投诉

KMP算法代码实现(java版)

package com.util;

import org.apache.log4j.Logger;

/**
* @author ycx
*
*/
public class KMPStringMatcher {
private static final Logger logger = Logger
.getLogger(KMPStringMatcher.class);
private char[] targetArr = null;
private char[] sourceArr = null;
private int[][] partionMatchTable = null;
private static final int NOT_MATCH = -1;

public static void main(String[] args) {
String target = "BBC ABCDAB ABCABCDABDDABCDABDE";
String match = "ABCDABD";

KMPStringMatcher kmp = new KMPStringMatcher(target);
System.out.println(kmp.find(match));


}

/**
* 构造器
*
* @param targetStr
*/
public KMPStringMatcher(String targetStr) {
if (targetStr == null)
throw new NullPointerException("target string can not be null");
this.targetArr = targetStr.toCharArray();
}

/**KMP算法匹配字符串的入口函数
* @param match
* @return
*/
public synchronized int find(String match) {
if (match == null)
throw new NullPointerException("match string can not be null");

char[] matchArr = match.toCharArray();
if (sourceArr == null || !isTwoCharArrEqual(sourceArr, matchArr)) {
calculatePartionMatchTable(matchArr);
sourceArr = matchArr;
}

if (targetArr.length < sourceArr.length)
return NOT_MATCH;

return getFirstPartionMatched(matchArr);

}

/**返回完全匹配的第一个字符位置
* @param matchArr
* @return
*/
private int getFirstPartionMatched(char[] matchArr) {
int i = 0, j = 0, moveStep = 0;
int firstPartion = NOT_MATCH;
while (j < matchArr.length && i < targetArr.length) {
if (matchArr[j++] != targetArr[i++]) {
moveStep = (j == 1) ? 1 : (j - 1 - partionMatchTable[1][j - 2]); //后移位数
i = i -j + moveStep;
j = 0;
continue;
}

if (j == matchArr.length) {
firstPartion = i - j;
break;
}
}

return firstPartion;

}

/**计算部分匹配表:算法的关键
*
* @param matcherString
* @return
*/
private boolean calculatePartionMatchTable(char[] m

第1页

你可能喜欢

热门文档

相关文档

  • KMP算法java实现

    KMP算法及其java实现 有如下字符串: 主串Sn:S1S2S3S4……Sn-1Sn 子串Pm:...算法结束 算法代码如下(代码为JAVA代码,字符数组首位并不是存数组长度): public...

  • KMP算法解析及其JAVA实现

    KMP算法解析及其JAVA实现_计算机软件及应用_IT/计算机_专业资料。字符串匹配的一种算法,使用JAVA语言实现以下根据数据结构(严蔚敏)书籍整理,代码写得比较难懂,有时间...

  • Java实现的KMP算法

    Java实现的KMP算法_计算机软件及应用_IT/计算机_专业资料。import java.util.Array...KMP算法解析及其JAVA实现... 4页 免费 KMP算法代码实现(java版... 2页 免费...

  • java实现的KMP算法

    java实现的KMP算法_计算机软件及应用_IT/计算机_专业资料。public class KMP { ...KMP算法解析及其JAVA实现... 4页 免费 KMP算法代码实现(java版... 2页 免费...

  • 用JAVA语言实现的KMP算法

    用JAVA语言实现的KMP算法_计算机软件及应用_IT/计算机_专业资料。用JAVA语言实现...KMP算法代码实现(java版... 2页 免费 c语言实现串匹配-KMP算法... 1页 1...

  • KMP算法C语言代码实现

    KMP算法C语言代码实现_IT/计算机_专业资料。KMP算法非改进型与改进型的next[]数组求值 及根据 next数组实现查找/*在Visual Studio 2008环境下调试*/ #include <st...

  • BF算法和KMP算法代码

    BF 算法 #include<iostream> #include<string.h> using namespace std; #...KMP算法C语言代码实现 5页 1下载券 字符串匹配之BM算法 2页 免费 模式匹配算法...

  • 【论文】基于MPI的两种数据分组方式的KMP算法的实现

    基于KMP算法的next函数理... 298人阅读 4页 2.00基于MP...116921)1—19—40 基于MP 的两 种数 据分 组方式的K P算法 的实现 IM ...

  • KMP算法伪代码

    KMP算法伪代码_计算机软件及应用_IT/计算机_专业资料。1. 在串 S 和串 T 中...KMP 算法 11页 免费 KMP算法c实现 4页 免费喜欢此文档的还喜欢 ...

  • 模式匹配中的KMP算法的实现

    字符串定位字串的方法比较多, 这里实现用 KMP 算法来实现模式穿的匹配, 给出模式串,要求程序求出其 Next[j]。KMP 匹配算法高效的部分就是此次匹配失败后下次 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email