题目描述

给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过 10000。

样例

输入："abab"

输出：True

解释：可由子字符串 "ab" 重复两次构成。

输入："aba"

输出：False

输入："abcabcabcabc"

输出：True

解释：可由子字符串 "abc" 重复四次构成，或者子字符串 "abcabc" 重复两次构成。

算法

(KMP) $O(n)$

1. 利用 KMP 算法求出原数组的 next 数组，next[i] 表示最长的 [0, next[i]] 的子串和以 s[i] 为结尾后缀相等的长度。
2. 利用 next数组的性质，考虑 next[n - 1] 即整个字符串的后缀和前缀相等的最大长度，若 next[n - 1] 不为 -1 且 n % (n - next[n - 1] - 1) == 0，则可以得到一个无重叠的循环节。可以根据 next 数组的性质进行证明正确性。

时间复杂度

• 时间复杂度和 KMP 相等，为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储 next 数组。

C++ 代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        vector<int> next(n);
        next[0] = -1;
        int j = -1;

        for (int i = 1; i < n; i++) {
            while (j >= 0 && s[i] != s[j + 1]) j = next[j];
            if (s[i] == s[j + 1])
                j++;
            next[i] = j;
        }

        return next[n - 1] != -1 && n % (n - next[n - 1] - 1) == 0;
    }
};