Leetcode 459. 重复的子字符串

给定一个非空的字符串 s ，检查是否可以通过由它的一个子串重复多次构成。

示例 1:

输入: s = “abab”
输出: true
解释: 可由子串 “ab” 重复两次构成。
示例 2:

输入: s = “aba”
输出: false
示例 3:

输入: s = “abcabcabcabc”
输出: true
解释: 可由子串 “abc” 重复四次构成。 (或子串 “abcabc” 重复两次构成。)

提示：

1 <= s.length <= 104
s 由小写英文字母组成

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        bool res = false;
        for(int i = 1; i <= s.size() / 2; i ++ ) {
            string a = s.substr(0, i);
            if(s.size() % i != 0) continue;
            int j = 0;
            for( ; j < s.size(); j += i ) {
                if(a == s.substr(j, i)) continue;
                else
                    break;
            }
            if(j == s.size()) {
                res = true;
                break;
            }
        }
        return res;
    }
};

KMP 做法：

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        // KMP 做法，朴素做法在CSDN
        int n = s.size();
        s = " " + s;
        vector<int> next(n + 1);
        for(int i = 2, j = 0; i <= n; i ++ ) {
            while(j && s[i] != s[j + 1]) j = next[j];
            if(s[i] == s[j + 1]) j ++;
            next[i] = j;
        }
        int t = n - next[n];
        return t < n && n % t == 0;
    }
};