LeetCode 1316. 不同的循环子字符串

给你一个字符串 text ，请你返回满足下述条件的 不同 非空子字符串的数目：
可以写成某个字符串与其自身相连接的形式（即，可以写为 a + a，其中 a 是某个字符串）。

例如，abcabc 就是 abc 和它自身连接形成的。

示例 1：
输入：text = "abcabcabc"
输出：3
解释：3 个子字符串分别为 "abcabc" ， "bcabca" 和 "cabcab" 。

示例 2：
输入：text = "leetcodeleetcode"
输出：2
解释：2 个子字符串为 "ee" 和 "leetcodeleetcode" 。

提示：
1 <= text.length <= 2000
text 只包含小写英文字母。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/distinct-echo-substrings

时间复杂度超高：

class Solution {
    public int distinctEchoSubstrings(String text) {
        HashSet<String> set = new HashSet<>();

        for(int i=0;i<text.length();i++){
            for(int j=i+1;2*j-i<=text.length();j++){
                String s1 = text.substring(i,j);
                String s2 = text.substring(j,2*j-i);
                if(s1.equals(s2))
                    set.add(s1);
            }
        }
        return set.size();
    }
}

来源：Rabin–Karp 算法

LeetCode官网给出的思路：

class Solution {

    private static final int BASE = 256;
    private static final int MOD = 101;
    private int[] mul; //基数
    private int[] prefix;//前缀数组,prefix[i]表示text[0,i)或text[0,i-1]的Hash值,共有i个字符
    private Set<String>[] sets;//为了减少碰撞，sets[i]保存长度为i的a+a字符串

    public int distinctEchoSubstrings(String text) {
        int len = text.length();
        mul = new int[len+1];
        prefix = new int[len+1];
        sets = new HashSet[len/2+1];
        mul[1] = 1;
        prefix[0]=0;
        for(int i=1;i<=len/2;i++) sets[i] = new HashSet<String>();
        for(int i=2;i<=len;i++) mul[i] = ( mul[i-1] * BASE ) % MOD;
        for(int i=1;i<=len;i++) prefix[i] = ( prefix[i-1] * BASE + text.charAt(i-1)) % MOD;
        for(int i=1;i<=len;i++){
            for(int j=i;j<=len;j++){
                int length = j-i+1; //[i,j],也就是从第(i+1)到第(j+1)个字符
                if(j+length<=len){
                    if( hash(i,j) == hash(j+1,j+length))
                        if(text.substring(i-1,j).equals(text.substring(j,j+length))){
                            String str = text.substring(i-1,j);
                            sets[length].add(str);
                            //System.out.println(text.substring(i-1,j));
                        }
                }
            }
        }
        int sum = 0;
        for(int i=1;i<=len/2;i++) sum+=sets[i].size();
        return sum;
    }

    private int hash(int a,int b){
        //prefix[i]是[1,i],prefix[j]是[1,j]
        //prefix[i] = text[0]*mul[i] + ... + text[i-1]*mul[i]
        //prefix[j] = text[0]*mul[1] + ... + text[i-1]*mul[i] + ... + text[j-1]*mul[j]
        return ( (prefix[b]-prefix[a-1]*mul[b-a+2]) % MOD + MOD ) % MOD;
    }
}

官网给出的题解：
using LL = long long;

class Solution {
private:
    constexpr static int mod = (int)1e9 + 7;
    
public:
    int gethash(const vector<int>& pre, const vector<int>& mul, int l, int r) {
        return (pre[r + 1] - (LL)pre[l] * mul[r - l + 1] % mod + mod) % mod;
    }
    
    int distinctEchoSubstrings(string text) {
        int n = text.size();
        
        int base = 31;
        vector<int> pre(n + 1), mul(n + 1);
        pre[0] = 0;
        mul[0] = 1;
        for (int i = 1; i <= n; ++i) {
            pre[i] = ((LL)pre[i - 1] * base + text[i - 1]) % mod;
            mul[i] = (LL)mul[i - 1] * base % mod;
        }
        
        unordered_set<int> seen[n];
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                int l = j - i;
                if (j + l <= n) {
                    int hash_left = gethash(pre, mul, i, j - 1);
                    if (!seen[l - 1].count(hash_left) && hash_left == gethash(pre, mul, j, j + l - 1)) {
                        ++ans;
                        seen[l - 1].insert(hash_left);
                    }
                }
            }
        }
        return ans;
    }
};

作者：LeetCode-Solution
来源：力扣（LeetCode）