<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:
        def build_suffix_array(s):
            """ Build suffix array for string s. """
            n = len(s)
            suffixes = sorted(range(n), key=lambda i: s[i:])
            rank = [0] * n
            for i, suffix in enumerate(suffixes):
                rank[suffix] = i
            return suffixes, rank

        def build_lcp(s, suffixes, rank):
            """ Build LCP array for the suffix array of string s. """
            n = len(s)
            lcp = [0] * (n - 1)
            h = 0
            for i in range(n):
                if rank[i] > 0:
                    j = suffixes[rank[i] - 1]
                    while i + h < n and j + h < n and s[i + h] == s[j + h]:
                        h += 1
                    lcp[rank[i] - 1] = h
                    if h > 0:
                        h -= 1
            return lcp

        n = len(text)
        suffixes, rank = build_suffix_array(text)
        lcp = build_lcp(text, suffixes, rank)
        seen = set()
        
        # Collect all distinct echo substrings
        for i in range(n):
            for length in range(1, (n - suffixes[i]) // 2 + 1):
                substring = text[suffixes[i]:suffixes[i] + 2 * length]
                if substring[:length] == substring[length:]:
                    seen.add(substring)
        
        return len(seen)

# Example usage
solution = Solution()
print(solution.distinctEchoSubstrings("abcabcabc"))  # Output: 3
print(solution.distinctEchoSubstrings("leetcodeleetcode"))  # Output: 2
18900