題目來源
給一個(gè)字符串，判斷是否是循環(huán)的，感覺就是找循環(huán)節(jié)。
怎么找循環(huán)節(jié)呢？
想不出來，看答案了…
可以利用KMP算法來做，
KMP需要先求出一個(gè)next數(shù)組，表示每個(gè)子串的公共前綴后綴。所以假如整個(gè)字符串的公共前綴后綴長度a是總長度n減去公共前綴后綴a的長度的倍數(shù)的話，
即a % (n - a) == 0那么該字符串就是repeated的。
這個(gè)方法確實(shí)很難想到。
代碼如下：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> dp(n+1, 0);
        int i = 1, j = 0;
        while (i < n) {
            if (s[i] == s[j])
                dp[++i] = ++j;
            else if (j == 0)
                i++;
            else
                j = dp[j];
        }
        return dp[n] && (dp[n] % (n - dp[n]) == 0);
    }
};