题解 | #kmp算法#

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        int i=0;
		int s=0;
        /*while((i=T.indexOf(S, i))!=-1) {
        	s++;
        	i++;
        }*/
		int[] arr = getnext(S);
		for(int j=i;i<T.length();i++,j++) {
			if(T.charAt(i)!=S.charAt(j)) {
				j=arr[j];
				if(j==-1) {
					continue;
				}
				//再来比一次
				i--;
				j--;
			}
			if(j==S.length()-1) {//匹配到了
				s++;
				j=arr[j]; // -------虽然匹配上了，但当做没匹配上，可以找到重叠的部分
			}
		}
		
		
        return s;
    }
    public static int[] getnext(String s) {
		int[] result = new int[s.length()];
		char ii, jj;
		/*
        双层循环生成数组，下面优化成动态规划单层循环生成
        for(int i =1;i<s.length();i++) { 
			ii = s.charAt(i);
			for(int j=i+1;j<s.length();j++) {
				jj=s.charAt(j);
				if(result[j-1]==i-1) {
					if(jj==ii) {
						result[j]=i;
					}
				}
			}
		}
		result[0]=-1;*/
		Arrays.fill(result, -1);
		for(int i=1;i<s.length();i++) {
			if(s.charAt(result[i-1]+1)==s.charAt(i)) {
				result[i]=result[i-1]+1;
			}else{
				result[i]=0;
			}
		}
		
		return result;
		
	}
}