<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:
    # optimize: power O(n) in python -> 
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        distinct = set()
        power = 26
        for length in range(1, n // 2 + 1):
            first_half = 0
            second_half = 0
            for i in range(0, n - length):
                first_half = first_half * 26 + (ord(text[i]) - ord('a'))
                second_half = second_half * 26 + (ord(text[i + length]) - ord('a'))
                if i >= length:
                    first_half = first_half - power * (ord(text[i - length]) - ord('a'))  # (26 ** length)
                    second_half = second_half - power * (ord(text[i]) - ord('a'))  # (26 ** length)

                if i >= length - 1 and first_half == second_half:
                    # print(text[i-(length-1):i+1])
                    distinct.add(text[i-(length-1):i+1])
            power *= 26

        return len(distinct)
17200