<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, text: str) -> int:
        P,M = 31, 10**9+7
        n = len(text)
        h = [[0 for _ in range(n)] for _ in range(n)]
        # rolling hash of string text; For 0<=i<=j<=n-1; h[i][j] = a[i]*p^(j-i) + a[i+1]*p^(j-i-1) +...+ a[j-1]*p^1 + a[j]*p^0, where a[k] = ord(text[k])-ord('a')+1

        for i in range(n):
            h[i][i] = ord(text[i])-ord('a')+1
            for j in range(i+1,n):
                h[i][j] = (h[i][j-1]*P % M+ ord(text[j])-ord('a')+1) % M
        
        count = {}
        for w in range(1,n//2+1): # w is the length of substring
            i = 0
            while i+2*w-1 <= n-1:                
                if h[i][i+w-1] == h[i+w][i+2*w-1]:
                    count[h[i][i+w-1]] = True
                i += 1

        return len(count)
        
111000