问题描述 链接到标题

686. 重复叠加字符串匹配 (Medium)

给定两个字符串 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

提示：

  • 1 <= a.length <= 10⁴
  • 1 <= b.length <= 10⁴
  • a 和 b 由小写英文字母组成

解题思路 链接到标题

对a，叠加至少(b.size() - 1) / a.size()，最多(b.size() - 1) / a.size() + 2次，然后利用kmp算法来匹配b和新的a。

代码 链接到标题 

class Solution {
public:
    bool check(string &s, string b) {
        vector<int> next(b.size());
        int x = 1, now = 0;
        while (x < b.size()) {
            if (b[x] == b[now]) {
                next[x++] = ++now;
            } else if (now == 0) {
                next[x++] = 0;
            } else {
                now = next[now - 1];
            }
        }
        int i = 0, j = 0;
        while (i < s.size() && j < b.size()) {
            if (s[i] == b[j]) {
                ++i;
                ++j;
            } else {
                if (j > 0) {
                    j = next[j - 1];
                } else {
                    ++i;
                }
            }
        }
        return j >= b.size();
    }
    int repeatedStringMatch(string a, string b) {
        int left = (b.size() - 1) / a.size();
        string s;
        if (left == 0) {
            s = a;
        } else {
           for (int i = 0; i < left; ++i) {
                s += a; 
           } 
        }
        for (int i = 0; i < 3; ++i) {
            if (check(s, b)) {
                return s.size() / a.size();
            } else {
                s += a;
            }
        }
        return -1;

    }
};