题目描述

给你一个字符串 text，请你返回满足下述条件的 不同 非空子字符串的数目：这些子字符串可以写成某个字符串与其自身的串联。

样例

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

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

限制

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

算法

(暴力枚举 + RK 哈希) $O(n^2)$

1. 首先介绍下字符串的 RK 哈希，也可以称为滚动哈希。将整个字符串看成一个 m 进制的数字（m >= 27），其中 a 对应 1，b 对应 2，依次类推，z 对应 27。将这个 m 进制字符串转为十进制数字作为哈希值。
2. 例如，当 m = 131，字符串为 abc 时，十进制为 1 * 131^2 + 2 * 131 + 3。我们求出以每个位置结尾的前缀哈希值，即 abc 就求出 a 和 ab 和 abc 的哈希值。整个过程可以在线性时间完成。
3. 但如果发生了溢出怎么办。如果不考虑溢出问题，每个字符串的哈希值都是唯一的。因为有溢出，所以需要进行取模运算，将哈希值对一个大质数取模（这将会导致哈希碰撞）。为了方便和减少碰撞率，我们以无符号 64 位整数来存储哈希值，并通过 C++ 自然溢出的处理方式来取模。（Leetcode 可能将溢出视为运行时异常，如果发生异常，则可以手动模一个大质数）。
4. 此时，可以很轻松求出两个区间字符串的哈希值。长度为 len 的区间 [s, s + len - 1] 的哈希值就是 h[s + len - 1] - h[s - 1] * base^len。以正常的十进制数字为例，例如求 1135 的最后两个数字 35，则可以让 1135 - 11 * 10^2。
5. 至此，可以暴力枚举所有的子串，然后用哈希值来判断是否满足要求。如果满足要求，再将其哈希值放进一个集合中去重。
6. 注意，这种解法会有一定的概率会发生哈希值冲突。

时间复杂度

• 预处理哈希值的时间复杂度为 $O(n)$。
• 共有 $O(n^2)$ 个子串，判断子串合法的时间复杂度为常数。
• 故总时间复杂度为 $O(n^2)$。

空间复杂度

• 需要额外 $O(n)$ 的空间记录哈希值。

C++ 代码

class Solution {
public:
    #define ULL unsigned long long
    ULL gethash(const vector<ULL> &h, const vector<ULL> &power,
                int s, int len) {
        return h[s + len - 1] - h[s - 1] * power[len];
    }

    int distinctEchoSubstrings(string text) {
        const int base = 131;
        int n = text.length();
        vector<ULL> h(n + 1), power(n + 1);

        power[0] = 1;
        for (int i = 1; i <= n; i++) {
            h[i] = h[i - 1] * base + text[i - 1] - 'a' + 1;
            power[i] = power[i - 1] * base;
        }

        unordered_set<ULL> v;

        for (int len = 2; len <= n; len += 2)
            for (int i = 1; i <= n - len + 1; i++) {
                ULL h1 = gethash(h, power, i, len / 2);
                ULL h2 = gethash(h, power, i + len / 2, len / 2);

                if (h1 == h2 && v.find(h1) == v.end())
                    v.insert(h1);
            }

        return v.size();
    }
};