在母串内查找子串 KMP 算法

之前了解了下这个算法，实现了下，有问题欢迎指教

package org.huangry.colorful.common.utils;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Arrays;

/**
 * ClassName: KMPUtil
 *
 * @author huangruiying
 * @version 1.0
 */
public class KMPUtil {

    private Logger logger = LoggerFactory.getLogger(KMPUtil.class);

    //计算后的序列
    private static int[] substring_sequence_arr;

    private String parentStr = "";
    private String childStr = "";

    public KMPUtil(String parentStr, String childStr){
        this.parentStr = parentStr;
        this.childStr = childStr;
        //处理子串:生成子串序列到substring_sequence_arr
        generate_substring_sequence(childStr);
        logger.info(">>> KMP init success");
        logger.info(">>> substr_seq_array {}",Arrays.toString(substring_sequence_arr));
    }

    /**
     * 查询母串内是否包含子串
     * 然后返回索引
     *  不包含时 索引为 -1
     *  包含时 索引为第一次出现的位置
     */
    public int start(){
        //通过KMP查询
        int index = search(parentStr,childStr);
        logger.info("子串在目标字符串的索引： {}", index);
        return index;
    }

    /**
     * 获取母串内包含子串的个数
     * @return
     */
    public int getCount(){
        return count(parentStr,childStr);
    }

    /**
     * KMP查询
     * @author huangruiying
     * @param target 目标字符串
     * @param substring 待查询子串
     * @return 查找到的子串在目标字符串中的起始索引
     */
    private int search(final String target, final String substring) {

        final char[] target_arr = target.toCharArray();
        final char[] substring_arr = substring.toCharArray();
        //初始化游标 i:target游标 j:子串游标
        int i=0,j=0;

        //边界
        while (i < target_arr.length){
            char target_val = target_arr[i];
            char substring_val = substring_arr[j];
            if(target_val == substring_val){
                //跳出条件 (-1 ： 长度跟索引比较，所以要-1)
                if(j == (substring.length()-1)){
                    /**
                     * 返回起始索引
                     * target&index:sssa&0123
                     * substr&index:sa&01
                     * 返回 （3-1）= 2 ， 2为substring sa第一字在target中出现的索引位置。
                     */
                    return i-j;
                }
                i++;
                j++;
            }else{
                int before_j = j - 1;
                //子串边界
                if(before_j < 0){
                    j = 0;
                }else{
                    j = substring_sequence_arr[before_j];
                }
                //未寻找到时的跳出条件
                if(i == (target.length()-1)){
                    return -1;
                }
            }
        }

        return -1;
    }

    private int count(final String target, final String substring) {

        int count = 0;// 计数 target 内包含多少个 substring

        final char[] target_arr = target.toCharArray();
        final char[] substring_arr = substring.toCharArray();
        //初始化游标 i:target游标 j:子串游标
        int i=0,j=0;

        //边界
        while (i < target_arr.length){
            char target_val = target_arr[i];
            char substring_val = substring_arr[j];
            if(target_val == substring_val){
                if(j == (substring.length()-1)){
                    count ++ ;
                    i ++ ;
                    j = 0;
                    continue;
                }
                i++;
                j++;
            }else{
                int before_j = j - 1;
                //子串边界
                if(before_j < 0){
                    j = 0;
                }else{
                    j = substring_sequence_arr[before_j];
                }
                //未寻找到时的跳出条件
                if(i == (target.length()-1)){
                    return count;
                }
                i ++ ;
            }
        }
        return count;
    }

    /**
     * 生成子串序列
     * 子串：abcdabca
     * 序列：00001231
     * 规则：使用i,j两游标，
     * 初始化变量i=0,j=1
     * 初始化序列数组 0 0 0 0 0 0 0 0
     * 对比i与j所在索引处的数组值是否相等
     * 若相等，那么j处序列数组值为i+1(索引+1) ，然后i，j分别向后移动一位
     * 若不相等，查看序列数组内当前i-1位置的值（索引），并将该值赋值给当前变量i 结束本次循环（注意i的边界情况）
     * @author huangruiying
     * @param substring 子串
     */
    private void generate_substring_sequence(String substring){
        substring_sequence_arr = new int[substring.length()];
        char[] substring_arr = substring.toCharArray();
        //游标
        int i=0,j=1;
        while (j<substring_arr.length){
            char iChar = substring_arr[i];
            char jChar = substring_arr[j];
            if(iChar == jChar){
                substring_sequence_arr[j] = i+1;
                j++;
                i++;
            }else{
                int before_i = i-1;
                //边界
                if(before_i < 0){
                    substring_sequence_arr[j] = 0;
                    j++;
                }else{
                    //通过序列内当前i的前一个值，改变i游标
                    i = KMPUtil.substring_sequence_arr[before_i];
                }
            }
        }
    }


}