如何将字符串分割为完全一致的重复子串？

我来帮你理清这个问题的正确解决思路，你之前用字符计数的方法其实有局限性——比如字符计数相同的字符串，可能字符顺序不同，没法正确判断重复子串的结构（比如"abab"和"aabb"字符数一样，但前者能拆分，后者不行）。

要把字符串拆分成完全相同的子串，本质是找到最小的重复单元，也就是字符串的最小周期。这里可以用KMP算法里的**前缀函数（部分匹配表）**来高效解决，步骤如下：

• 计算前缀函数数组：前缀函数prefix[i]表示字符串s[0..i]中，最长的相等前缀和后缀的长度。
• 确定最小周期长度：假设字符串长度为n，前缀函数最后一个值为prefix[n-1]。如果n % (n - prefix[n-1]) == 0，那么最小周期长度就是n - prefix[n-1]；否则整个字符串就是唯一的子串。
• 拆分字符串：用最小周期长度截取子串，重复拆分原字符串即可。

import java.util.ArrayList;
import java.util.List;

public class StringPatternSplitter {
    public static List<String> findPattern(String s) {
        List<String> result = new ArrayList<>();
        int n = s.length();
        if (n == 0) {
            return result;
        }

        // 计算前缀函数数组
        int[] prefix = new int[n];
        for (int i = 1; i < n; i++) {
            int j = prefix[i-1];
            while (j > 0 && s.charAt(i) != s.charAt(j)) {
                j = prefix[j-1];
            }
            if (s.charAt(i) == s.charAt(j)) {
                j++;
            }
            prefix[i] = j;
        }

        int cycleLength = n - prefix[n-1];
        // 判断是否存在重复周期
        if (n % cycleLength == 0) {
            String pattern = s.substring(0, cycleLength);
            // 拆分字符串
            for (int i = 0; i < n / cycleLength; i++) {
                result.add(pattern);
            }
        } else {
            // 没有重复周期，直接加入原字符串
            result.add(s);
        }

        return result;
    }

    public static void main(String[] args) {
        // 测试示例
        System.out.println(findPattern("abcabcabcabc")); // ["abc", "abc", "abc", "abc"]
        System.out.println(findPattern("aaaaaa")); // ["a", "a", "a", "a", "a", "a"]
        System.out.println(findPattern("abc")); // ["abc"]
    }
}

• 前缀函数计算：通过迭代比较当前字符和前缀的末尾字符，逐步更新前缀函数值，时间复杂度为O(n)，非常高效。
• 周期判断逻辑：比如对于"abcabcabcabc"，长度n=12，前缀函数最后值是9，12-9=3，12%3=0，所以周期长度是3，对应子串"abc"，拆分4次得到结果。
• 特殊情况处理：当字符串没有重复周期（比如"abc"），直接将原字符串加入结果列表。

字符计数只能统计每个字符出现的次数，但无法反映字符的顺序。比如"abbaabba"和"aaaabbbb"的字符计数完全相同，但前者可以拆分成["abba", "abba"]，后者却无法拆分成完全相同的子串，所以这个方法不能准确判断重复子串的结构。

内容的提问来源于stack exchange，提问作者Aditya Verma