<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>

class Solution:
    def distinctEchoSubstrings(self, s: str) -> int:
        BASE = 29
        MOD = 1000000007
        n = len(s)
        hash_vals = [0] * (n + 1)
        pow_vals = [1] * (n + 1)
        
        for i in range(1, n + 1):
            hash_vals[i] = (hash_vals[i - 1] * BASE + ord(s[i - 1])) % MOD
            pow_vals[i] = pow_vals[i - 1] * BASE % MOD
        
        def get_hash(l: int, r: int) -> int:
            return (hash_vals[r] - hash_vals[l] * pow_vals[r - l] % MOD + MOD) % MOD

        seen_hashes = set()
        
        for i in range(n):
            for length in range(2, n - i + 1, 2):
                mid = i + length // 2
                hash1 = get_hash(i, mid)
                hash2 = get_hash(mid, i + length)
                if hash1 == hash2:
                    seen_hashes.add(hash1)
        
        return len(seen_hashes)

16600