459.重复的子字符串——学习笔记

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

示例 1：

输入: s = "abab"
输出: true
解释: 可由子串 "ab" 重复两次构成。

示例 2：

输入: s = "aba"
输出: false

示例 3：

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

提示：

• 1 <= s.length <= $10^4$
• s 由小写英文字母组成

题目来源：力扣（LeetCode）链接

题解：

• 方法一：移动匹配
  字符串 abcabc
  

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 拼接 s+s，去除 s+s 的首字母和尾字符
        String t = (s + s).substring(1, 2 * s.length() - 1);
        // 如果新字符串里面还有一个 s，则说明 s 是由重复字符串组成的
        return t.contains(s);
    }
}

• 方法二：KMP 算法
  在由重复子串组成的字符串中，最长相等前后缀不包含的子串就是最小重复子串
  
  • 举例说明
    

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 如果为 ""，直接返回 false
        if (s.equals("")) {
            return false;
        }
        int len = s.length;
        // 求出字符串 s 的前缀表
        int[] next = new int[len];
        int j = 0;
        next[0] = j;
        for (int i = 0; i < len; i++) {
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = next[j];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        // 如果最长相同前后缀不为 0，且字符串长度是最长相等前后缀不包含的子串长度的倍数
        // 就说明字符串是由最长相等前后缀不包含的子串重复组成的
        if (next[len - 1] > 0 && len % (len - next[len - 1]) == 0) {
            return true;
        }
        return false;
    }
}