算法

(KMP) $O(n)$

$KMP$算法对于next数组的应用。 next[i]是指对于字符串s[0,i-1]中，前缀与后缀的最大匹配长度。 例如对于"abcabcabc"来说，其next[8] = 5，也即对于s[0,7]="abcabcab"，前缀与后缀最大匹配的串为"abcab"，长度为5。 用字符串长度减1减去最后一位的next数组值之后得到的应为重复串的长度。

C++ 代码

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int l = s.length();
        vector<int> next(l);
        next[0] = -1;
        int i, j = -1;
        for (i = 1; i < l; i++) {
            while (j >= 0 && s[i] != s[j + 1]) {
                j = next[j];
            }
            if (s[i] == s[j + 1]) {
                j++;
            }
            next[i] = j;
        }
        int lenSub = l - 1 - next[l - 1];
        return lenSub != l && l % lenSub ==0;
    }
};