1316. Distinct Echo Substrings

1316. Distinct Echo Substrings (Hard)

Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string).

 

Example 1:

Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:

Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

 

Constraints:

• 1 <= text.length <= 2000
• text has only lowercase English letters.

Related Topics:
String, Rolling Hash

Solution 1. Rolling Hash

// OJ: https://leetcode.com/problems/distinct-echo-substrings/
// Author: github.com/lzl124631x
// Time: O(N^2)
// Space: O(N)
class Solution {
public:
    int distinctEchoSubstrings(string s) {
        int N = s.size(), mod = 1e8 + 7, cnt = 0;
        vector<long> v(N);
        for (int len = 1; len <= N / 2; ++len) {
            long hash = s[0] - 'a', p = 1;
            unordered_set<string> seen;
            for (int i = 1; i < N; ++i) {
                if (i < len) {
                    hash = (hash * 26 + s[i] - 'a') % mod;
                    p = (p * 26) % mod;
                } else {
                    hash = ((hash - (s[i - len] - 'a') * p) * 26 + s[i] - 'a') % mod;
                    if (hash < 0) hash += mod;
                    if (i - 2 * len + 1 >= 0 && v[i - len] == hash) {
                        auto a = s.substr(i - 2 * len + 1, len);
                        if (seen.count(a)) continue;
                        seen.insert(a);
                        if (a == s.substr(i - len + 1, len)) ++cnt;
                    }
                }
                v[i] = hash;
            }
        }
        return cnt;
    }
};