<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:
        # Get all the substring and chekc if they have the same hash value or n ot
        # First we need to calculate the hash. 
        # There are two ways, calculate on the fly (does not use extra space, this will not suit this problem) 
        # We will try the other way to keep track of the hashed value 
        n = len(text)
        base = 256 
        mod = 10**9+7
        text_hash = [0]*(n+1) 
        
        for i in range(1, n+1): 
            text_hash[i] = (text_hash[i-1]*base % mod) + ord(text[i-1])

        def check(s, e): 
            # m is lower then size is better, maybe there i sb 
            # abcabc. Neu chia cho 2 thi con abcabc (0+6)/2
            m = (s+e+1)//2 
            # First word start from s to m-1 inclusive 
            # Second word start from m to e inclusive 
            # Hash of first work 
            l =  m-s
            # Wrong in getting this one
            first_word_hash = ((text_hash[m] - text_hash[s]*pow(base,l, mod)) % mod)
            # Hash of second word
            second_word_hash = ((text_hash[e+1] - text_hash[m]*pow(base, l, mod)) % mod)
            if first_word_hash == second_word_hash: 
                return True 
            else:
                return False 

        res = set()
        # Get all the substrings 
        # There are two ways, I remember one with the length and the other is not
        for s in range(n): 
            for e in range(s, n): 
                l = e-s+1 
                if l % 2 != 0: 
                    continue
                else: 
                    if check(s, e):
                        res.add(text[s:e+1])
        print(res)
        return len(res)  
19600