来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/repeated-string-match
题目描述
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
示例 1： 输入：a = "abcd", b = "cdabcdab" 输出：3 解释：a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。 示例 2： 输入：a = "a", b = "aa" 输出：2 示例 3： 输入：a = "a", b = "a" 输出：1 示例 4： 输入：a = "abc", b = "wxyz" 输出：-1
解题思路
对于这种问题，暴力法也叫朴素求解法是将两个字符串一个一个比较，可以肯定复杂度为O(mn)，但是通过KMP算法，可以将复杂度下降到O(m+n).
KMP算法的原理是，在匹配过程中，匹配字符串之中会有重复的字符，遍历过后如果使用朴素算法，会有多次的遍历，可以使用一个next数组，将有相同前缀的标记起来，在遍历的时候便可以跳过遍历前缀的过程，大大提高了解题效率
next数组构建过程如下：（借用宫水三叶大佬的两张图）
这样，在两个字符串比较过程中，如果发现字符比较不相同，可以直接跳到与当前字符串有相同前缀的字符上，不需要从头开始进行计算。
代码展示
class Solution { public: int strStr(string haystack, string needle) { int m = haystack.size(); int n = needle.size(); if(n == 0) return 0; int iRet = 0; vector<int> viNext(n, 0); for(int i = 1, j = 0; i < n; i++) { while(needle[i] != needle[j] && j > 0) { j = viNext[j - 1]; } if(needle[i] != needle[j]) { viNext[i] = 0; } else { viNext[i] = j + 1; j++; } } for(int i = 0, j = 0; i < m; i++) { while(haystack[i] != needle[j] && j > 0) { j = viNext[j - 1]; } if(haystack[i] != needle[j]) { j = 0; } else { j++; } if(j == n) { return i - n + 1; } } return -1; } };
运行结果
