686. Repeated String Match

ad-hoc O(n*(n+m)) m是A的长度 n是B的长度

class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        string s;
        int cnt = 0;
        while (s.length() < B.length()) {
            ++cnt;
            s += A;
        }
        if (s.find(B) != string::npos) return cnt;
        s += A; // 长度超过B未必一定包含B有可能最后还差A开头的几个字母
        ++cnt;
        return s.find(B) == string::npos ? -1 : cnt;
    }
};

这道题还有KMP和Rabin-Karp (Rolling Hash)两种做法 O(m+n)但是过于复杂

class Solution {
public:
    int repeatedStringMatch(string A, string B) {
        string s;
        int cnt = 0;
        while (s.length() < B.length()) {
            ++cnt;
            s += A;
        }
        if (strStr(s, B) != -1) return cnt;
        s += A; // 长度超过B未必一定包含B有可能最后还差A开头的几个字母
        ++cnt;
        return strStr(s, B) == -1 ? -1 : cnt;
    }

    int strStr(const string &haystack, const string &needle) {
        int h = haystack.length(), n = needle.length();
        long M = INT_MAX, B = 256; // INT_MAX是质数！
        if (h < n) return -1;
        long highest_power = 1, hh = 0, nh = 0;
        for (int i = 0; i < n; ++i) {
            highest_power = (highest_power * B) % M;
            nh = (nh * B + needle[i]) % M;
            hh = (hh * B + haystack[i]) % M;
        }
        for (int i = 0; i <= h - n; ++i) {
            if (i >= 1) {
                hh = (hh * B + M - haystack[i - 1] * highest_power % M + haystack[i + n - 1]) % M; // 这里highest_power是B的n次方，因为先整体左移再减高位，如果先减高位再整体左移就是n-1次方了
            }
            if (hh == nh && haystack.substr(i, n) == needle) return i;
        }
        return -1;
    }
};