KMP算法

package mediumdifficulty;


import java.util.Arrays;

/*
KMP算法，返回一个字符串在另一个字符串中出现的频率
 */
public class NC149 {

    public static void main(String[] args) {
        NC149 demo = new NC149();
        String text="abababab";
        String pattern="ababab";

        int count = demo.kmp(pattern, text);
        System.out.println(count);
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * <p>
     * 计算模板串S在文本串T中出现了多少次
     *
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp(String S, String T) {
        // write code here
        int M = S.length();
        int N = T.length();
        if(N==0||M==0)return 0;
        int[] lps = createLPSArray(S);
//        System.out.println(Arrays.toString(lps));
        int i = 0, j = 0;
        int counter=0;

        while (i < N) {
            while (T.charAt(i) == S.charAt(j)) {
                i++;
                j++;
                if(j==M){
                    counter++;
                    j=lps[j-1];
                }
                if(i==N)break;
            }
            if(j==0){
                i++;
            }else {
                j=lps[j-1];
            }
        }
        return counter;

    }

    /**
     * 创建模板字符串p的lps数组
     *
     * @param p
     * @return
     */
    private int[] createLPSArray(String p) {
        int M = p.length();
        int i = 1, j = 0;
        int[] lps = new int[M];
        //lps[i]代表p[0,...i]中既是前缀（不包括整个字符串）又是后缀的最大长度
        // 例如"ABCAB"的前缀包括"A"、"AB"、"ABC"、"ABCB"
        //后缀包括"BCAB"、"CAB"、"AB"、"B"
        lps[0] = 0;
        while (i < M) {
            //当i和j匹配，
            if (p.charAt(i) == p.charAt(j)) {
                j++;
                lps[i] = j;
                i++;
            } else {
                if (j == 0) {
                    lps[i] = 0;
                    i++;
                } else {
                    j = lps[j - 1];
                }
            }
        }

        return lps;
    }
}