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 <= 2000text has only lowercase English letters.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);
}