題目來源
給兩個字符串，問第一個字符串的子串最多能有多少個第二個字符串重復(fù)的數(shù)目膜蠢。差不多是這個意思。
然后我一開始想的是找循環(huán)節(jié)莉兰，剩下的再遍歷下挑围，但是超時了。代碼如下：

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        int p1 = 0, p2 = 0, cycle1 = 0, cycle2 = 0;
        bool isCycle = false;
        while (p1 < n1 * s1.size()) {
            if (s1[p1 % s1.size()] == s2[p2 % s2.size()])
                p2++;
            p1++;
            if (p1 % s1.size() == 0 && p2 % s2.size() == 0) {
                cycle1 = p1 / s1.size();
                cycle2 = p2 / s2.size();
                isCycle = true;
                break;
            }
        }
        int cnt = 0;
        if (isCycle) {
            int cycleNum = n1 * s1.size() / p1;
            cnt += cycleNum * cycle2;
            p1 = cycleNum * p1;
            p2 = cnt * s2.size();
            while (p1 < n1 * s1.size()) {
                if (s1[p1 % s1.size()] == s2[p2 % s2.size()])
                    p2++;
                p1++;
            }
        }
        cnt = p2 / s2.size();
        return cnt / n2;
    }
};

看了下tags糖荒，用的DP杉辙，想一想怎么做。錯誤例子的情況應(yīng)該是找不到循環(huán)節(jié)的捶朵？想不到應(yīng)該怎么做…
然后我就又跑去看答案了…
主要分為三個部分蜘矢，一個前綴，一個循環(huán)的部分综看，一個后綴品腹。然后把三者加起來。然后找循環(huán)的部分主要是通過nextIndex[start] == k這么一個方法來找的红碑。

class Solution {
public:
    int getMaxRepetitions(string s1, int n1, string s2, int n2) {
        vector<int> repeatCount(s2.size() + 1, 0);
        vector<int> nextIndex(s2.size() + 1, 0);
        int k = 0, cnt = 0;
        for (int i=1; i<=n1; i++) {
            for (int j=0; j<s1.size(); j++) {
                if (s1[j] == s2[k])
                    k++;
                if (k == s2.size()) {
                    k = 0;
                    cnt++;
                }
            }
            repeatCount[i] = cnt;
            nextIndex[i] = k;
            for (int start = 0; start < i; start++) {
                if (nextIndex[start] == k) {
                    int prefixCount = repeatCount[start];
                    int patternCount = (repeatCount[i] - repeatCount[start]) * (n1 - start) / (i - start);
                    int suffixCount = repeatCount[start + (n1 - start) % (i - start)] - repeatCount[start];
                    return (prefixCount + patternCount + suffixCount) / n2;
                }
            }
        }
        return repeatCount[n1] / n2;
    }
};