一、核心：        

        当出现字符串不匹配时，可以记录一部分之前已经匹配的文本内容，利用这些信息避免从头再去做匹配，因此需要一个数组记录已经匹配的文本内容。

        对于字符串匹配问题，暴力法也叫朴素求解法是将两个字符串一个一个的比较，时间复杂度为O(mn)，但是通过KMP算法，可以将时间复杂度下降到O(m+n)。

二、next数组

        next数组是一个前缀表，前缀表是用来回退的，它记录了模式串与主串不匹配的时候，模式串应该从哪里开始重新匹配。

• 前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串；
• 后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

        前缀表要求相同前后缀的长度。【最长公共前后缀】

        模式串与前缀表对应位置的数字表示：下标 i 之前（包括 i ）的字符串中，有多大长度的相同前缀后缀。

  参考代码：

void getNext(vector<int>& nextv, const string& needle) {nextv[0] = 0;for(int i=1, j=0; i<needle.size(); ++i) {while(j > 0 && needle[i] != needle[j]) {//回退j = nextv[j-1];}if(needle[i] == needle[j]) {nextv[i] = j + 1;j++;}}
}

三、代码

问题：找出字符串中第一个不匹配的下标

class Solution {
public:int strStr(string str, string needle) {if(needle.size() == 0) return 0;vector<int> nextv(needle.size(), 0); //定义next数组getNext(nextv, needle); //计算next数组for(int i=0,j=0; i<str.size(); ++i) {while(j > 0 && str[i] != needle[j]) {j = nextv[j - 1];}if(str[i] == needle[j]) {j++;}if(j == needle.size()) {return (i - j + 1);}}return -1;}
};

问题2：重复叠加字符串匹配

        思路：首先找到b串第一次出现的位置；然后计算a串重复的次数。

        解释：对于a串重复的次数部分，当确定了b串的第一次出现的位置index后，如果a串的大小减去index后依然比b串的大小大，那么a串完全覆盖b串，此时返回1；如果a串剩余的部分比b串小，那么将重复n次的a串根据index斩头去尾然后除以a串的大小，即b串内部需要a串重复的次数，进而加上头与尾超出的部分两次，即最终的n。

class Solution {
public:int KMP(string a, string b) {//if(b.size() == 0) return 0;vector<int> nextv(b.size(), 0);for(int i=1, j=0; i<b.size(); ++i) {while(j > 0 && b[i] != b[j]) {//b[i] != b[j]j = nextv[j - 1];}if(b[i] == b[j]) {nextv[i] = j + 1;j++;}}for(int i=0, j=0; i<a.size()+b.size(); ++i) {while(j > 0 && a[i%a.size()] != b[j]) {//a[i%a.size()]j = nextv[j - 1];}if(a[i%a.size()] == b[j]) {j++;}if(j == b.size()) {return i-j+1;}}return -1;}int repeatedStringMatch(string a, string b) {//1.获取第一次出现的位置int res = KMP(a, b);//2.计算a串重复次数if(res != -1) {if(a.size() - res >= b.size()) {res = 1;}else {res = 2 + (b.size() - a.size() + res - 1)/a.size();}}return res;}
};