KmpUtils

以前对算法不是很经常用，趁着项目中有个关于字符串匹配的问题；
为优化之前的代码，写几个模式匹配的类

/**
 * KMP算法工具类O(M + N)
 * String.indexOf()看起来像是暴力匹配，算法复杂度O（N^2）
 * @author kevin
 * 测试结果取样：
 * System.nanoTime
 * 普通耗时：9443
 * KMP耗时：6979
 * **/


public class KmpUtils {

    /**
     * 不对外暴露该方法
     * 模式串的部分匹配表
     * 紧凑的关系
     * ps：后一个的匹配数量值，是基于前一个匹配值的 长度（k） 加一得到的；
     * 如果不匹配，则前缀匹配串，需要从头重新验证匹配关系
     * @param patternString 模式串
     * **/
    private static int[] getNext(String patternString) {
        char[] chars = patternString.toCharArray();
        int[] next = new int[chars.length];

        int j = 0;
        int k = -1;
        next[0] = -1;

        // 根据前一个j位的匹配长度，验证第j+1位
        while (j < chars.length - 1) {
            if (k == -1 || chars[j] == chars[k]) {
                next[++j] = ++k;
            } else {
                k = next[k];
            }
        }

        return next;
    }

    /**
     * 把握要点：源字符串位置不前移，针对目标模式串进行移动
     * 这样可以减少移动匹配的次数
     * **/
    public static boolean indexOf(String source, String target) {
        char[] sourceChars = source.toCharArray();
        char[] targetChars = target.toCharArray();

        // 源字符串的位置
        int i = 0;
        // 目标模式串的位置
        int j = 0;

        int[] next = getNext(target);
        while (i < sourceChars.length && j < targetChars.length) {
            // j = -1时，j重新置为0；只向后移动i
            if (j == -1 || sourceChars[i] == targetChars[j]) {
                i++;
                j++;
            } else {// j指向指定位置，即目标模式串移动指向
                j = next[j];
            }
        }
        return  j == targetChars.length;
    }

    /**
     * 模糊匹配的方式
     * **/
    public static String fuzzyMatching(String source, String target){
        //长度过分了
        if(target.length() > source.length()){
            return "";
        }
        int tempI = 0;
        int tempJ = 0;

        char[] sourceChars = source.toCharArray();
        char[] targetChars = target.toCharArray();

        // 源字符串的位置
        int i = 0;
        // 目标模式串的位置
        int j = 0;

        int[] next = getNext(target);
        while (i < sourceChars.length && j < targetChars.length) {
            if (j == -1 || sourceChars[i] == targetChars[j]) {
                i++;
                j++;
                //当长度 > 当前长度时，重新赋值
                if(j > tempJ || tempJ == 0){
                    tempI = i;
                    tempJ = j;
                }
            } else {
                j = next[j];
            }
        }

        if(tempJ <= 0 ){
            return "";
        }

        char[] matchChars = new char[tempJ];
        int n = 0;
        for(int m = tempI - tempJ; m < tempI ; m++){
            matchChars[n++] = sourceChars[m];
        }

        return String.valueOf(matchChars);
    }
}