重复的子字符串

发表于 更新于 分类于

算法-重复的子字符串

背景

  • 算法–重复的子字符串

  • 博主以代码随想录算法公开课进行学习

题目

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

    示例 1:

    • 输入: “abab”
    • 输出: True
    • 解释: 可由子字符串 “ab” 重复两次构成。

    示例 2:

    • 输入: “aba”
    • 输出: False

    示例 3:

    • 输入: “abcabcabcabc”
    • 输出: True
    • 解释: 可由子字符串 “abc” 重复四次构成。 (或者子字符串 “abcabc” 重复两次构成。)

思路

  • 判断字符串s是否由某个子串重复多次构成，核心逻辑基于 KMP 的「最长相等前后缀」：

  • 设字符串长度为len，其前缀表（next 数组）的最后一个值为next[len-1]。

    如果满足两个条件：

    • len % (len - next[len-1]) == 0（字符串长度能被「长度 - 最长相等前后缀长度」整除）；
    • next[len-1] != 0（存在非空的最长相等前后缀）。则字符串s可以由子串s[0 : len - next[len-1]]重复构成。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        int[] next = new int[n];
        int j = 0;
        next[0] = 0;
        for(int i = 1;i < n;i++){
            while(j > 0&&s.charAt(j) != s.charAt(i)){
                j = next[j - 1];
            }
            if(s.charAt(j) == s.charAt(i)){
                j++;
            }
            next[i] = j;
        }
         // 3. 核心判断：是否由重复子串构成
        // 条件1：next[n-1] > 0 → 存在非空的最长相等前后缀
        // 条件2：n % (n - next[n-1]) == 0 → 总长度能被「非前后缀部分的长度」整除
        if(next[n - 1]>0&&n%(n-next[n-1])==0){
            return true;
        }else{
            return false;
        }
    }
}

总结

  • next 数组的核心作用：记录模式串每个位置的最长相等前后缀长度，避免暴力匹配的重复遍历；
  • 关键公式：最小重复子串长度 = 字符串总长度 - 最长相等前后缀长度，若总长度能被该值整除，则存在重复子串