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.

1316. Distinct Echo Substrings
``````struct Solution;

use std::collections::HashSet;

const MOD: i64 = 1_000_000_007;
const PRIME: i64 = 29;

impl Solution {
fn distinct_echo_substrings(text: String) -> i32 {
let text: Vec<u8> = text.bytes().collect();
let n = text.len();
let mut hs: HashSet<i64> = HashSet::new();
for i in 1..=n / 2 {
let mut j = 0;
let mut k = i;
let mut hash1 = 0;
let mut hash2 = 0;
let mut m = 1;
for _ in 0..i {
m *= PRIME;
m %= MOD;
}
while k < n {
hash1 = (hash1 * PRIME + (text[j] - b'a' + 1) as i64) % MOD;
hash2 = (hash2 * PRIME + (text[k] - b'a' + 1) as i64) % MOD;
if j >= i {
hash1 = (MOD + hash1 - ((text[j - i] - b'a' + 1) as i64 * m) % MOD) % MOD;
hash2 = (MOD + hash2 - ((text[k - i] - b'a' + 1) as i64 * m) % MOD) % MOD;
}
j += 1;
k += 1;
if j >= i && hash1 == hash2 {
hs.insert(hash1);
}
}
}
hs.len() as i32
}
}

#[test]
fn test() {
let text = "abcabcabc".to_string();
let res = 3;
assert_eq!(Solution::distinct_echo_substrings(text), res);
let text = "leetcodeleetcode".to_string();
let res = 2;
assert_eq!(Solution::distinct_echo_substrings(text), res);
let text = "abcabcabcabcabcabcabcabcabc".to_string();
let res = 12;
assert_eq!(Solution::distinct_echo_substrings(text), res);
}
``````