LeetCode 686. 重复叠加字符串匹配

原题链接
题目描述：
给定两个字符串 a 和 b，寻找重复叠加字符串 a 的最小次数，使得字符串 b 成为叠加后的字符串 a 的子串，如果不存在则返回 -1。
注意：字符串 "abc" 重复叠加 0 次是 ""，重复叠加 1 次是 "abc"，重复叠加 2 次是 "abcabc"。
思路
字符串b想要匹配a字符串，实际上a并不是无限的增加，只需要增加到一定长度即可。因为如果增长的a字符串长度超过了b字符串，但是由于a字符串是周期性增长，所以如果前面已经包含了b的一部分中，b不是这一部分的子串，那么后面无论如何也不会让b成为子串。增长到超过b长度的字符串记为S，S与b的匹配就是典型的KMP算法。a增长了几次就是匹配的字符下标对a的长度向上取整
代码

class Solution {
public:
    int repeatedStringMatch(string a, string b) {
        string S;
        while(S.size() < b.size()) S+=a;
        S+=a;
        int n=S.size(),m=b.size();
        S=' '+S,b=' '+b;
        //处理Ne数组
        vector<int> Ne(m+1);

        for(int i=2,j=0;i<=m;i++){
            while(j && b[i] != b[j+1]) j=Ne[j];
            if(b[i] == b[j+1]) j++;
            Ne[i]=j;
        }

        //匹配
        for(int i=1,j=0;i<=n;i++){
            while(j && S[i] != b[j+1]) j=Ne[j];
            if(S[i] == b[j+1]) j++;
            if(j == m){
                return (i+a.size()-1)/a.size();
            }
        }
        return -1;
    }
};