题意概述

给定一个模式串S和一个文本串T
要求得到模式串S在文本串T中出现的次数

方法一：Brute_Force算法（朴素模式匹配算法超时）

思路与具体做法

同时遍历文本串和模式串
- 如果两串对应位相等，接着比较下一位
- 如果不相等，令模式串回到上一次开始匹配位置的下一位，而文本串从头开始比较
- 遍历完一遍模式串，令出现次数加一

class Solution {
public:
    int kmp(string S, string T) {
        int i=0,j=0,ans=0;
        while(i<T.size()){
            if(T[i]==S[j]){//两串对应位相等，接着比较下一位 
                i++;j++;
            }else{//不相等，令模式串回到上一次开始匹配位置的下一位，而文本串从头开始比较 
                i=i-j+1;
                j=0;
            }
            if(j==S.size())ans++;//遍历完一遍模式串，令出现次数加一
        }
        return ans;//返回出现次数 
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O ((n - m) * m)$ ,最坏情况下每次遍历到串的最后一个字符，下标j都要置0，共需遍历 $(n - m + 1) * m$ 次
空间复杂度： $O (1)$ 仅定义了几个整形变量

方法二：KMP算法

思路与具体做法

step1：求模式串的next数组(程序中next数组使用改进后的，即nextval数组)
- 初始i指向模式串第一个字符，j指向i的前一个字符。以j为子串首，i为子串尾，对[j,i]内的子串求最长相等前后缀长度
- 接着遍历模式串
  - 如果子串首尾相等即S[i]==S[j]则ij++比较各对应的下一位或对应位不相等但前缀指针j已经回退到起点即j=0，则后缀指针i++正常遍历前缀指针j++才能从起点指向第一个元素，然后继续比较前后缀长度
    - S[i]==S[j]后缀指针i所对应的最大相等前缀j的前缀next[j]
    - S[i]!=S[j]后缀指针i所对应的最大相等前缀j 或 j=0后缀指针i的最长相等前后缀长度为0
  - 否则对应位不相等时且前缀指针i仍可回退，让i回退，即指向它的最大相等前缀下标
step2：KMP算法
- 同时遍历文本串和模式串
  - 当对应位相等的时候或模式串指针回溯到起点时都没不匹配，都直接匹配下一位
  - 否则模式串指针向前回溯
  - 同时遍历过程中，每遍历完一遍模式串，令出现次数加一（KMP模板则是直接返回查找到的下标）

class Solution {
public:
    int Next[500500];
	void Get_Next(string S,int Next[]){//求模式串的next数组 
		Next[1]=0;
		int i=1,j=0;//初始i指向模式串第一个字符，j指向i的前一个字符。以j为子串首，i为子串尾，对[j,i]内的子串求最长相等前后缀长度 
		while(i<S.size()){//遍历模式串 
			if(j==0||S[i]==S[j]){//S[i]==S[j]即子串首尾相等 或 j=0对应位不相等但前缀指针j已经回退到起点，接着ij++，继续比较前后缀长度 
				++i;//S[i]==S[j]前后缀都相等时则比较各对应的下一位 或 j=0后缀指针i++正常遍历前缀指针j++才能从起点指向第一个元素 
				++j;
				if(S[i]==S[j])Next[i]=Next[j];//S[i]==S[j]后缀指针i所对应的最大相等前缀j的前缀next[j]
				else Next[i]=j;//S[i]!=S[j]后缀指针i所对应的最大相等前缀j 或  j=0后缀指针i的最长相等前后缀长度为0 
			}else j=Next[j];//对应位不相等时且前缀指针i仍可回退，让i回退，即指向它的最大相等前缀下标 
		}
	}
    int kmp(string S, string T) {
        S=""+S;//方便从下标为1开始求next数组
        T=""+T;
        Get_Next(S,Next);
        int i=1,j=1,ans=0;
        while(i<T.size()){//同时遍历文本串和模式串 
            if(j==0||T[i]==S[j]){//当对应位相等的时候 或 模式串指针回溯到起点时都没不匹配，都直接匹配下一位 
                i++;
                j++; 
            }else j=Next[j];//模式串指针向前回溯 
            if(j==S.size()){//遍历完一遍模式串，令出现次数加一 
                ans++;
                j=Next[j];
            }
        }
        return ans;//返回出现次数 
    }
};

时间复杂度和空间复杂度分析

时间复杂度： $O (m + n)$ 预处理求模式串的next数组耗时 $O (m)$ , KMP算法遍历了一次文本串耗时 $O (n)$
空间复杂度： $O (m)$ 用到了大小为m的辅助数组next

题解 | #kmp算法#

题意概述

方法一：Brute_Force算法（朴素模式匹配算法超时）

思路与具体做法

时间复杂度和空间复杂度分析

方法二：KMP算法

相关知识

思路与具体做法

时间复杂度和空间复杂度分析