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 <= 2000texthas 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();
}
}