Count The Repetitions

题目来源
给两个字符串，问第一个字符串的子串最多能有多少个第二个字符串重复的数目。差不多是这个意思。
然后我一开始想的是找循环节，剩下的再遍历下，但是超时了。代码如下：

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，想一想怎么做。错误例子的情况应该是找不到循环节的？想不到应该怎么做…
然后我就又跑去看答案了…
主要分为三个部分，一个前缀，一个循环的部分，一个后缀。然后把三者加起来。然后找循环的部分主要是通过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;
    }
};