KMP算法-Java实现

KMP算法之Java实现

相关代码

各位前来看这篇文章，目的也就是获取相关的代码，这里开门建山，给出可以使用的核心的代码：

/**
 * 用于字符串匹配的工具
 * 
 * @author kevin
 * 
*/
public class StringKmp {

/**
 * 用于计算匹配的位置（从头到尾）
 * @param str
 * @param sub
 * @return
 */
    public static int kmp(String str, String sub) {
if(str == null || sub == null || str.length() == 0 || sub.length() == 0){
            throw new IllegalArgumentException("str或者sub不能为空");
        }

int j = 0;
int[] n = next(sub);
for (int i = 0; i < str.length(); i++) {
while(j > 0 && str.charAt(i) != sub.charAt(j)){
                j = n[j - 1];
            }

if(str.charAt(i) == sub.charAt(j)){
                j++;
            }

if(sub.length() == j){
int index = i - j + 1;
return index;
            }
        }

return -1;
    }

    /**
     * 用于生成部分匹配表
     * @param sub
 * @return
 */
 private static int[] next(String sub) {
int[] n = new int[sub.length()];
int x = 0;
for (int i = 1; i < sub.length(); i++) {
while (x > 0 && sub.charAt(x) != sub.charAt(x)) {
x = n[x - 1];
            }

if (sub.charAt(i) == sub.charAt(x)) {
x++;
            }

            n[i] = x;
        }
return n;
    }

}

演示代码

public class Main {
    public static void main(String[] args) {
        String str = "BBC ABCDAB ABCDABCDABDE";
        String sub = "ABCDAB";

int index = StringKmp.kmp(str, sub);
        System.out.println("index-->"+index);
    }
}

输出结果

index-->4

KMP的理解

网络中已经有了很好的相关解释，本人水平有限，理解也不是很透彻，所以请移步到篇博客
代码参考：请点击这里，可能需要*

结语

目前Java没有提供关于KMP相应的jar包，可以将上述代码直接当做工具类来使用。

转载请标明出处http://blog.csdn.net/qq_26411333/article/details/51622537