字符串简单2 种解法

#459重复的子字符串

判断非空字符串能否由某个更短子串重复若干次构成。

#字符串#字符串匹配#KMP

解题主线

若 s 具有周期，s 一定会出现在 (s + s) 去掉首尾字符后的内部。

KMP 的最长相等真前后缀长度为 L 时，候选周期为 n - L；它必须整除 n。

解法 1：双倍字符串

在 s+s 中从下标 1 开始找 s；若首次匹配位置小于 n，则存在非平凡旋转周期。

时间复杂度

O(n²) 最坏，取决于 String.indexOf 的朴素匹配

空间复杂度

O(n)

459. 重复的子字符串 · 双倍字符串

java

final class Solution {
    public boolean repeatedSubstringPattern(String s) {
        String doubled = s + s;
        return doubled.indexOf(s, 1) < s.length();
    }
}

在 s+s 中从下标 1 开始找 s；若首次匹配位置小于 n，则存在非平凡旋转周期。

解法 2：KMP 前缀函数

构造每个前缀的最长相等真前后缀长度，用最终边界推导最短周期。

时间复杂度

O(n)

空间复杂度

O(n)

459. 重复的子字符串 · KMP 前缀函数

java

final class Solution {
    public boolean repeatedSubstringPattern(String s) {
        int n = s.length();
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            int matched = prefix[i - 1];
            while (matched > 0 && s.charAt(i) != s.charAt(matched)) {
                matched = prefix[matched - 1];
            }
            if (s.charAt(i) == s.charAt(matched)) matched++;
            prefix[i] = matched;
        }
        int border = prefix[n - 1];
        int period = n - border;
        return border > 0 && n % period == 0;
    }
}

构造每个前缀的最长相等真前后缀长度，用最终边界推导最短周期。

边界与易错点

不能把完整 s+s 的首个位置 0 当作周期证据。
逐个旋转虽然可行，但 O(n²) 且反复复制，已替换为线性 KMP。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

easy/Q459_repeatedSubstringPattern.java