# 1316. Distinct Echo Substrings

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.

``````class Solution {
public:
int distinctEchoSubstrings(string text) {
unordered_set<string> st;
int n = text.size();
for (int len = 1; len <= n / 2; ++len) {
for (int i = 0, j = len, cnt = 0; i < n - len; ++i, ++j) {
if (text[i] == text[j]) ++cnt;
else cnt = 0;
if (cnt == len) {
st.insert(text.substr(i, len));
--cnt;
}
}
}
return st.size();
}
};
``````

`(a * BASE^3 + b * BASE^2 + c * BASE^1 + d * BASE^0) % M`

``````class Solution {
public:
int distinctEchoSubstrings(string text) {
unordered_set<long> st;
int n = text.size(), BASE = 29, M = 1e9 + 7;
vector<long> hash(n + 1), power(n + 1);
power[0] = 1;
for (int i = 1; i <= n; ++i) {
hash[i] = (hash[i - 1] * BASE + text[i - 1]) % M;
power[i] = power[i - 1] * BASE % M;
}
for (int i = 0; i < n; ++i) {
for (int len = 2; i + len <= n; len += 2) {
int mid = i + len / 2;
long hash1 = getHash(i, mid, hash, power, M);
long hash2 = getHash(mid, i + len, hash, power, M);
if (hash1 == hash2) st.insert(hash1);
}
}
return st.size();
}
long getHash(int i, int j, vector<long>& hash, vector<long>& power, int M) {
return (hash[j] - hash[i] * power[j - i] % M + M) % M;
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1316

Find Substring With Given Hash Value

https://leetcode.com/problems/distinct-echo-substrings/

https://leetcode.com/problems/distinct-echo-substrings/discuss/492704/Intuitive100-Sliding-Counter-(with-pictures)

https://leetcode.com/problems/distinct-echo-substrings/discuss/477217/Java-Brute-force-and-Hash-Solution-Clean-code

LeetCode All in One 题目讲解汇总(持续更新中…)

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

|

Venmo 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation