题意整理

• 给定模式串S和主串T。
• 求模式串S在主串T中出现的次数。

方法一（朴素模式匹配）

1.解题思路

• 首先进行特殊情况判断，如果模式串长度大于主串，或者主串为空，返回0。
• 然后分别遍历主串和模式串，只要当前字符相等，模式串和主串均后移一位，如果不相等，模式串重新回退到索引0的位置，同时主串索引i回退到上次匹配开头的位置。
• 当模式串索引达到长度m时，说明全部匹配上了。此时将匹配次数加一，同时主串索引i回退到上次匹配开头的下一位，模式串索引j回到0。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        int m=S.length(),n=T.length();
        //特殊情况判断
        if(m>n||n==0) return 0;
        //出现次数
        int cnt=0;
        //分别遍历主串和模式串
        for(int i=0,j=0;i<n;i++){
            //只要不相等，模式串回退到0位置
            while(j>0&&T.charAt(i)!=S.charAt(j)){
                i=i-j+1;
                j=0;
            }
            if(T.charAt(i)==S.charAt(j)) j++;
            //如果j等于m，说明所有字符都匹配上了
            if(j==m){
                //次数加一，同时i回退到上次匹配开头的下一位，j回到0
                cnt++;
                i=i-j+2;
                j=0;
            }
        }
        return cnt;
    }
    
}

3.复杂度分析

• 时间复杂度：最坏情况下，比如主串是"000001"，匹配串是"001"，每次到匹配串的最后一个字符，其下标j都要重新置0回到开头，所以需要遍历 次，复杂度是 。
• 空间复杂度：需要额外常数级别的内存空间，所以空间复杂度为 。

方法二（kmp模式匹配）

1.解题思路

朴素模式匹配之所以慢，是因为每次字符不相等时，模式串要回退到初始位置。可以利用之前的匹配信息排除掉多余的回退，关键点就是建立一个next数组来记录模式串索引应该回退的位置，接下来分析怎么确定next数组。

比如模式串为"ababab"时，next数组是[0,0,1,2,3,4]

确定next数组思路：主要是根据之前是否有重复前缀字串来确定应该跳到什么位置，首先索引0位置，没有信息可以参考，直接回退到0；索引1位置，a和b不相等，没有重复前缀字串，直接回退到0；索引2位置，这时候有公共前缀a，回退到前缀的下一个索引1；索引3位置，这时候有公共前缀ab，回退到前缀的下一个索引2；索引4位置，这时候有公共前缀aba，回退到前缀的下一个索引3；索引5位置，这时候有公共前缀abab，回退到前缀的下一个索引4（上面所说的公共前缀尽可能取最长的）。

基本步骤：

• 首先进行特殊情况判断，与朴素方法一致。
• 然后分别遍历主串和模式串，只要当前字符相等，模式串和主串均后移一位，如果不相等，模式串重新回退到next数组指定的下一位索引。
• 当模式串索引达到长度m时，说明全部匹配上了。此时将匹配次数加一，同时模式串索引j回退到next数组指定的下一位索引。

遍历的过程中，除了模式串可以直接回退到next数组指定的下一位外，还有一个优化点，即每完成一次匹配，主串不需要回退了。

动图展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 计算模板串S在文本串T中出现了多少次
     * @param S string字符串 模板串
     * @param T string字符串 文本串
     * @return int整型
     */
    public int kmp (String S, String T) {
        //特殊情况判断
        int m=S.length(),n=T.length();
        if(m>n||n==0) return 0;
        
        //初始化计数，获取next数组
        int cnt=0;
        int[] next=getNext(S);
        
        //遍历主串和模式串
        for(int i=0,j=0;i<n;i++){
            //只要不相等，回退到next数组记录的下一位
            while(j>0&&T.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            if(T.charAt(i)==S.charAt(j)) j++;
            //如果j为m，说明完全匹配一次
            if(j==m){
                //计数加一，索引回退到next数组记录的下一位
                cnt++;
                j=next[j-1];
            }
        }
        return cnt;
    }
    
    //确定next数组
    private int[] getNext(String S){
        int m=S.length();
        int[] next=new int[m];
        for(int i=1,j=0;i<m;i++){
            //只要不相等，回退到next数组记录的下一位
            while(j>0&&S.charAt(i)!=S.charAt(j)){
                j=next[j-1];
            }
            //前缀索引后移
            if(S.charAt(i)==S.charAt(j)) j++;
            //确定应该回退到的下一个索引
            next[i]=j;
        }
        return next;
    }
    
}

3.复杂度分析

• 时间复杂度：预处理出next数组需要 的时间复杂度，而匹配的过程需要遍历一遍主串，复杂度为，所以总的时间复杂度是 。
• 空间复杂度：需要额外大小为m的next数组，所以空间复杂度为。