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".
usestd::collections::HashSet;constBASE:u64=131;implSolution{#[allow(dead_code)]pubfndistinct_echo_substrings(text:String)->i32{letn=text.len();letmutvis:HashSet<u64>=HashSet::new();letmutbase_vec:Vec<u64>=vec![1;n+1];letmuthash_vec:Vec<u64>=vec![0;n+1];// Initialize the base vector & hash vectorforiin0..n{letcur_char=((text.chars().nth(i).unwrap()asu8)-('a'asu8)+1)asu64;// Update base vectorbase_vec[i+1]=base_vec[i]*BASE;// Update hash vectorhash_vec[i+1]=hash_vec[i]*BASE+cur_char;}// Traverse the text to find the result pair, using rolling hashforiin0..n-1{forjini+1..n{// Prevent overflowletk=i+(j-i)/2;letleft=Self::get_hash(i+1,k+1,&base_vec,&hash_vec);letright=Self::get_hash(k+2,j+1,&base_vec,&hash_vec);ifleft==right{vis.insert(left);}}}vis.len()asi32}#[allow(dead_code)]fnget_hash(start:usize,end:usize,base_vec:&Vec<u64>,hash_vec:&Vec<u64>)->u64{hash_vec[end]-hash_vec[start-1]*base_vec[end-start+1]}}