Formatted question description: https://leetcode.ca/all/1316.html

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/

// 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;
    }
};

Java

class Solution {
    public int distinctEchoSubstrings(String text) {
        Set<String> substringsSet = new HashSet<String>();
        int length = text.length();
        for (int i = 0; i < length; i++) {
            int maxLength = length - i;
            for (int j = 2; j <= maxLength; j += 2) {
                String substr1 = text.substring(i, i + j / 2), substr2 = text.substring(i + j / 2, i + j);
                if (substr1.equals(substr2))
                    substringsSet.add(substr1 + substr2);
            }
        }
        return substringsSet.size();
    }
}

// OJ: https://leetcode.com/problems/distinct-echo-substrings/
// 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;
    }
};

```
print("Todo!")
```

1316 - Distinct Echo Substrings

1316. Distinct Echo Substrings (Hard)

Solution 1. Rolling Hash

All Problems

All Solutions