<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 Node:
    def __init__(self):
        self.adj = None
        self.isWord = False

class Trie:
    def __init__(self):
        self.root = Node()
        self.dp = dict()
    
    def addWord(self, word):
        def dfs(word, node):
            if len(word) == 0:
                node.isWord = True
                return
            if node.adj == None:
                node.adj = [None] * 26
            idx = ord(word[0]) - ord("a")
            if node.adj[idx] != None:
                dfs(word[1:], node.adj[idx])
            else:
                newNode = Node()
                node.adj[idx] = newNode
                dfs(word[1:], newNode)
        dfs(word, self.root)
    
    def search(self, word):
        def dfs(word, node, ctr, name):
            # if name in self.dp:
            #     return self.dp[name]
            if len(word) == 0:
                # self.dp[name] = ctr > 0
                # return self.dp[name]
                return True
            if node.isWord:
                if dfs(word, self.root, ctr + 1, name):
                    return True
            if node.adj == None:
                return False
            idx = ord(word[0]) - ord("a")
            if node.adj[idx] != None:
                if dfs(word[1:], node.adj[idx], ctr, name):
                    return True
            return False
        return dfs(word, self.root, 0, word)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        ans = 0
        s = set()
        for i in range(n-1):
            for j in range(i+1, n+1):
                a = text[i:j]
                if a in s:
                    continue
                l = j - i
                if l % 2 == 0:
                    if a[0:l // 2] == a[l//2 : ]:
                        s.add(a) 
                        ans += 1
                else:
                    continue
        print(s)
        return ans
        
        
20600