题解 | #kmp算法#

kmp分两步，第一是确定模板串S的数组，第二是与文本串T进行对比。

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public void main(String[] args){
        Scanner scan = new Scanner(System.in);
        String str=scan.nextLine();
//      String strReplace=str.replace('"','');
        String[] strSplit =str.split(",");
        String S = strSplit[0];
        String T=strSplit[1];
        int kmpCnt=kmp(S,T);
        System.out.print(kmpCnt);
    }
    public int kmp (String S, String T) {
        // write code here
        //第一步确定Next数组
        int[] index = Index(S);
        //第二步开始比对
        int indexT=0;int indexS=0;int kmpCnt=0;
        while(true){
            if(T.length()-indexT < S.length()-indexS)
                break;
            if(T.charAt(indexT)==S.charAt(indexS)){
                indexS++;indexT++;
                if(indexS==S.length()){
                    kmpCnt++;
                    indexS=index[indexS-1];
                }
            }else{
                if(indexS==index[indexS]){
                    indexS=0;indexT++;
                }else
                    indexS=index[indexS];
            }
        }
        return kmpCnt;
    }
    public int[] Index(String S){
        int[] index = new int[S.length()];
        int indexPos=0;int indexCur=1;int repeatCnt=0;
        while(indexCur<S.length()){
            if(S.charAt(indexCur)==S.charAt(indexPos)){
                ++repeatCnt;
                index[indexCur]=repeatCnt;
                indexPos++;
            }
            else{
                repeatCnt=0;indexPos=0;
            }
            indexCur++;
        }
        return index;
    }
}