字符串专题.md

重复的连续子串

适用问题

• 在一个字符串中寻找出现次数大于等于2的连续子串
• 判断这样的子串是否存在
• 找最长或最短出现次数大于等于2的连续子串
• ...

模板

long[] h, p;
int P = 131313;

public .. Solution(String s, int len) {
    int n = s.length();
    List<String> res = new ArrayList<>();
    h = new long[n + 10];
    p = new long[n + 10];
    p[0] = 1;
    for (int i = 1; i <= n; i++) {
        h[i] = h[i - 1] * P + s.charAt(i - 1);
        p[i] = p[i - 1] * P;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 1; i + len - 1 <= n; i++) {
        int j = i + len - 1;
        int hash = h[j] - h[i - 1] * p[j - i + 1];
        int cnt = map.getOrDefault(hash, 0);
        if (cnt == 1) res.add(s.substring(i - 1, i + len - 1));
        map.put(hash, cnt + 1);
    }
}

如果给定了要找的重复子串的长度，那么len就是题意。如果没有给定长度而是要求找最大或者最小长度，那么就使用二分来确定len，可以参考 1044.最长重复子串 这道题

字符串的子串