Distinct Echo Substrings
<p>Return the number of <strong>distinct</strong> non-empty substrings of <code>text</code>&nbsp;that can be written as the concatenation of some string with itself (i.e. it can be written as <code>a + a</code>&nbsp;where <code>a</code> is some string).</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;abcabcabc&quot;
<strong>Output:</strong> 3
<b>Explanation: </b>The 3 substrings are &quot;abcabc&quot;, &quot;bcabca&quot; and &quot;cabcab&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> text = &quot;leetcodeleetcode&quot;
<strong>Output:</strong> 2
<b>Explanation: </b>The 2 substrings are &quot;ee&quot; and &quot;leetcodeleetcode&quot;.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= text.length &lt;= 2000</code></li>
	<li><code>text</code>&nbsp;has only lowercase English letters.</li>
</ul>
Trie; String; Hash Function; Rolling Hash
use std::collections::HashSet;

const BASE: u64 = 131;

impl Solution {
    #[allow(dead_code)]
    pub fn distinct_echo_substrings(text: String) -> i32 {
        let n = text.len();
        let mut vis: HashSet<u64> = HashSet::new();
        let mut base_vec: Vec<u64> = vec![1; n + 1];
        let mut hash_vec: Vec<u64> = vec![0; n + 1];

        // Initialize the base vector & hash vector
        for i in 0..n {
            let cur_char = ((text.chars().nth(i).unwrap() as u8) - ('a' as u8) + 1) as u64;
            // Update base vector
            base_vec[i + 1] = base_vec[i] * BASE;
            // Update hash vector
            hash_vec[i + 1] = hash_vec[i] * BASE + cur_char;
        }

        // Traverse the text to find the result pair, using rolling hash
        for i in 0..n - 1 {
            for j in i + 1..n {
                // Prevent overflow
                let k = i + (j - i) / 2;
                let left = Self::get_hash(i + 1, k + 1, &base_vec, &hash_vec);
                let right = Self::get_hash(k + 2, j + 1, &base_vec, &hash_vec);
                if left == right {
                    vis.insert(left);
                }
            }
        }

        vis.len() as i32
    }

    #[allow(dead_code)]
    fn get_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]
    }
}
