题解 | #kmp算法#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    /**********************************************************************************/
    // 暴力破解法
    /*
    public int kmp (String S, String T) {
        // write code here
        int res = 0;
        int ls = S.length();
        int lt = T.length();
        for (int i = 0; i <= lt - ls; i++) {
            String str = T.substring(i, i + ls);
            if (S.equals(str)) {
                res++;
            }
        }
        return res;
    }
    */

    /**********************************************************************************/
    // KMP
    /*
    public int getIndexOf(String s, String m) {
        if (s == null || m == null || m.length() < 1 || s.length() < m.length()) {
            return -1;
        }
        char[] schar = s.toCharArray();
        char[] mchar = m.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int[] next = getNextArray(schar);
        while (i1 < schar.length && i2 < mchar.length) {
            if (schar[i1] == mchar[i2]) {
                i1++;
                i2++;
            } else if (next[i2] == -1) {
                i1++;
            } else {
                i2 = next[i2];
            }
        }
        return i2 == mchar.length ? i1 - i2 : -1;
    }

    public int[] getNextArray(char[] chrs) {
        if (chrs.length == 1) {
            return new int[]{-1};
        }
        int[] next = new int[chrs.length];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {
            if (chrs[i - 1] == chrs[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
    */

    /**********************************************************************************/
    // KMP(改)
    public int kmp (String S, String T) {
        if (S == null || T == null || S.length() < 1 || S.length() > T.length()) {
            return 0;
        }
        char[] schar = T.toCharArray();
        char[] mchar = S.toCharArray();
        int i1 = 0;
        int i2 = 0;
        int res = 0;
        int[] next = getNextArray(mchar);
        while (i1 < schar.length) {
            if (i2 == -1 || schar[i1] == mchar[i2]) {
                i1++;
                i2++;
            } else {
                i2 = next[i2];
            }
            if (i2 == mchar.length) {
                res++;
                i2 = next[i2];
            }
        }
        return res;
    }

    public int[] getNextArray(char[] chrs) {
        if (chrs.length == 1) {
            return new int[] {-1};
        }
        int[] next = new int[chrs.length + 1];
        next[0] = -1;
        next[1] = 0;
        int i = 2;
        int cn = 0;
        while (i < next.length) {
            if (chrs[i - 1] == chrs[cn]) {
                next[i++] = ++cn;
            } else if (cn > 0) {
                cn = next[cn];
            } else {
                next[i++] = 0;
            }
        }
        return next;
    }
}