459. 重复的子字符串

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

示例 1:

输入: "abab"

输出: True

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

示例 2:

输入: "aba"

输出: False

示例 3:

输入: "abcabcabcabc"

输出: True

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

解法

1. 暴力解法

遍历先找到与第一个与首字符 s[0] 相等的字符 s[i]，判断此时走过的子串是否为循环子串，依次判断 s[1] == s[i + 1] ... s[i - 1] == s[i + i - 1] ，如果出现不相等的字符再依次找到下一个与首字符相等的字符并循环判断即可。这种方法在字符串很长的时候很容易超时。由于这种方法需要频繁进行子串匹配操作，可以借助 KMP 的思路来进行优化一下。

2. KMP

KMP算法，获取整个字符串的相等最长前后缀长度数组 next，数组长度为 len，如果 next[len - 1] != 0那么此时数组字符串存在相等的前后缀，如果字符串是由循环子串组成，那么此时子串的长度为 len - next[len - 1]，如果len % (len - (next[len - 1])) == 0，则说明字符串长度是子串长度的整数倍，此时字符串是由该子串循环组成。

假设字符串 s 使用多个重复子串构成（这个子串是最小重复单位），重复出现的子字符串长度是 x，所以 s 是由 n * x 组成。

因为字符串 s 的最长相同前后缀的长度一定是不包含 s 本身，所以 最长相同前后缀长度必然是 m * x，而且 n - m = 1

所以如果 nx % (n - m)x = 0，就可以判定有重复出现的子字符串。

public boolean repeatedSubstringPattern(String s) {
    // 计算 next 数组
    int[] next = new int[s.length()];
    next[0] = 0;
    int j = 0;
    for (int i = 1; i < next.length; i++) {
        while (j > 0 && s.charAt(i) != s.charAt(j)) {
            j = next[j - 1];
        }
        if (s.charAt(i) == s.charAt(j)) {
            j++;
        }
        next[i] = j;
    }

    // 获取最长相同前后缀长度
    int n = next[s.length() - 1];
    if(n == 0){
        return false;
    }
    // 获取子串长度
    int subLen = s.length() - n;
    // 判断字符串长度是否为子串长度的整数倍
    return s.length() % subLen == 0;
}