LeetCode 459. 重复的子字符串

Categories:

题目描述
思路分析
1. 解法一：字符串拼接（推荐）
2. 解法二：KMP next 数组
相似题目

题目描述

✅ 459. 重复的子字符串

思路分析

解法一：字符串拼接（推荐）

核心思路：

若字符串 s 由某子串重复多次构成，则将 s 与自身拼接得到 s+s。

去掉 s+s 的首尾各一个字符，所得字符串中必然包含原字符串 s。

反过来，若不是重复子串构成，去掉首尾后就找不到 s。

去掉首字符是为了排除从位置 0 开始的匹配（即原串本身），去掉尾字符是为了排除从末尾开始的匹配。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串 s 的长度，字符串拼接与查找均为 O(n)。

空间复杂度：O(n)，其中 n 表示字符串 s 的长度，需要额外存储拼接后的字符串。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        // 将 s 拼接成 s+s，去掉首尾字符后检查是否包含原字符串 s
        String doubled = s + s;
        String trimmed = doubled.substring(1, doubled.length() - 1);
        return trimmed.contains(s);
    }
}

func repeatedSubstringPattern(s string) bool {
    doubled := s + s
    // 去掉首尾字符后检查是否包含原字符串 s
    trimmed := doubled[1 : len(doubled)-1]
    return strings.Contains(trimmed, s)
}

解法二：KMP next 数组

核心思路：

利用 KMP 算法中的 next 数组（部分匹配表）来判断。

next[i] 表示 s[0..i] 中最长公共前后缀的长度。

若 s 可以由子串重复构成，则最小重复单元的长度为 n - next[n-1]。

当 n % (n - next[n-1]) == 0 且 next[n-1] != 0 时，s 由重复子串构成。

next[n-1] != 0 是必要条件，排除无重复子串的情况（如 "abcd"，next[3]=0，n%(n-0)=0 需排除）。

复杂度分析：

时间复杂度：O(n)，其中 n 表示字符串 s 的长度，构建 next 数组为 O(n)。

空间复杂度：O(n)，其中 n 表示字符串 s 的长度，需要额外存储 next 数组。

class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        int[] next = buildNext(s);
        // 最小重复单元长度为 n - next[n-1]
        // 若 n 能被该长度整除，且存在公共前后缀，则由重复子串构成
        int len = n - next[n - 1];
        return next[n - 1] != 0 && n % len == 0;
    }

    private int[] buildNext(String s) {
        int n = s.length();
        int[] next = new int[n];
        // next[0] 固定为 0，从索引 1 开始构建
        int j = 0;
        for (int i = 1; i < n; 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;
        }
        return next;
    }
}

func repeatedSubstringPattern(s string) bool {
    n := len(s)
    next := buildNext(s)
    // 最小重复单元长度为 n - next[n-1]
    // 若 n 能被该长度整除，且存在公共前后缀，则由重复子串构成
    length := n - next[n-1]
    return next[n-1] != 0 && n%length == 0
}

func buildNext(s string) []int {
    n := len(s)
    next := make([]int, n)
    // next[0] 固定为 0，从索引 1 开始构建
    j := 0
    for i := 1; i < n; i++ {
        // 不匹配时，回退到上一个最长公共前后缀位置
        for j > 0 && s[i] != s[j] {
            j = next[j-1]
        }
        // 匹配时，公共前后缀长度加一
        if s[i] == s[j] {
            j++
        }
        next[i] = j
    }
    return next
}

相似题目

题目	难度	考察点
28. 找出字符串中第一个匹配项的下标	简单	KMP / 字符串匹配
686. 重复叠加字符串匹配	中等	字符串拼接 / KMP
214. 最短回文串	困难	KMP / 字符串构造
1392. 最长快乐前缀	困难	KMP / 字符串前缀
796. 旋转字符串	简单	字符串拼接判断
572. 另一棵树的子树	简单	序列化 + 字符串匹配

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/36043259