kmp算法

1，概念

kmp算法就是根据模式字符串匹配目标字符串

2，kmp算法原理

1）求出模式字符串的所有子串的最长前缀和后缀相等的长度，并求出next数组

例如，题目给的ababab

它的所有字串有：

a
ab
aba
abab
ababa
ababab

对应的最长相等的前缀后缀：

0
0
1
2
3
4

这些数值对应next数组的值，转成next数组

3）匹配过程

f和b匹配失败，会将模式串pre指针定位到前一位取出对应的next[pre-1]，将pre的值更新为该next[pre-1]，然后跳到对应的pre，这一部这样处理的原因是：模式串里f前面aabaa是已经匹配过了，找出模式串aabaa最长相等前后缀，aabaa的最长相等前后缀是aa，就跳到模式串aa后面的b然后重新匹配后面的字符串，因为目标串b前面的aa是匹配过的，如果aabaaf的f无法匹配成功，就跳到上个最长相等前后缀匹配，即模式串aa开始的前缀，重新匹配模式字符串aa后面的字符，如果依然匹配不上，就继续找上上个最长相等前后缀，直到pre=0

3，实现过程

1）初始化

2）找出next数组

3）匹配数组

4，找出目标串里面模式串的数量

在匹配到模式串最后一个字符后面的位置，则数量加1，然后跳到上个最长相等前后缀的位置

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        int[] next=new int[S.length()];
        int pre=0;
        next[0]=0;
        for(int sufix=1;sufix<S.length();sufix++){
            while(pre>0&&S.charAt(pre)!=S.charAt(sufix)){
                pre=next[sufix-1];
            }
            if(S.charAt(pre)==S.charAt(sufix)){
                pre++;
            }
            next[sufix]=pre;
        }
        
        pre=0;
        int num=0;
        for(int sufix=0;sufix<T.length();sufix++){
            while(pre>0&&T.charAt(sufix)!=S.charAt(pre)){
                pre=next[pre-1];
            }
            if(T.charAt(sufix)==S.charAt(pre)){
                pre++;
            }
            if(pre==S.length()){
                num++;
                pre=next[pre-1];
            }
        }
        return num;
        
    }
    
}