Return the number of distinct non-empty substrings of text that can be written as the concatenation of some string with itself (i.e. it can be written as a + a where a is some string).
 
Example 1:
Input: text = "abcabcabc"
Output: 3
Explanation: The 3 substrings are "abcabc", "bcabca" and "cabcab".

Example 2:
Input: text = "leetcodeleetcode"
Output: 2
Explanation: The 2 substrings are "ee" and "leetcodeleetcode".

 
Constraints:

1 <= text.length <= 2000
text has only lowercase English letters.

Difficulty: interview

Starter code:

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        

Solutions:
# class Solution:
#     def distinctEchoSubstrings(self, text: str) -> int:
#         ans = set()
        
#         for i in range(len(text)-1): 
#             for j in range(i+1, (i+len(text))//2+1): 
#                 if text[i:j] == text[j:2*j-i]: ans.add(text[i:j])
        
#         return len(ans)
from collections import defaultdict, deque
class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        if all(x==text[0] for x in text):
            # handle worst case seperately
            return len(text)//2
        
        res = set()
        character_locations = defaultdict(lambda:deque())
        for i, c in enumerate(text):
            for j in character_locations[c]:
                if i + (i - j) > len(text): break
                    
                # Use startswith to improve result slightly                    
                if text.startswith(text[i:i+i-j], j):
                    res.add(text[j:i+i-j])
                    
            character_locations[c].appendleft(i)
            
        return len(res)

from collections import defaultdict, deque
class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        if all(x==text[0] for x in text):
            # handle worst case seperately
            return len(text)//2
        
        res = set()
        character_locations = defaultdict(lambda:deque())
        for i, c in enumerate(text):
            for j in character_locations[c]:
                if i + (i - j) > len(text): break
                    
                # Use startswith to improve result slightly                    
                if text.startswith(text[i:i+i-j], j):
                    res.add(text[j:i+i-j])
                    
            character_locations[c].appendleft(i)
            
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        ans = set()
        
        for i in range(len(text)-1): 
            for j in range(i+1, (i+len(text))//2+1): 
                if text[i:j] == text[j:2*j-i]: ans.add(text[i:j])
        
        return len(ans)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        
        seen = set()
        
        count = 0
        
        for i in range(len(text)-1):
            for j in range(i, len(text), 1):
                # h = j//2
                # l = h - i
                
                l=(j-i+1)//2
                h=l+i
                
                # print(text[i:h], text[h:h+l], i, j)
                if l<1 or text[i:h+l] in seen: continue
                
                if text[i:h] == text[h:h+l]:
                    count += 1
                    # print( '**', text[i:h+l])
                    seen.add(text[i:h+l])
                    
                    
        return count
    
    
#     2 7
    
#     l=(j-i+1)//2
#     h=l//2
    
    
#     0 8
    
#     0:4 4:4+(8-0)//2


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        
        seen = set()        
        count = 0
        
        for i in range(len(text)-1):
            for j in range(i, len(text), 1):
                l=(j-i+1)//2
                h=l+i
                t = text[i:h+l]
                
                # print(text[i:h], text[h:h+l], i, j)
                if l<1 or t in seen: continue
                
                if t[:l] == t[l:]:
                    count += 1
                    # print( '**', text[i:h+l])
                    seen.add(t)
                    
                    
        return count



class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        def pos (s):
            
            n = len (s)
            if n%2 != 0:
                return False
            
            for i in range (n//2):
                if s[i] != s[i+(n//2)]:
                    return False
                
            return True
        
        res = set()
        for i in range (len(text)-1):
            for j in range (i+1, len(text), 2):
                m = i + ((j-i+1)//2)
                if hash (text[i:m]) == hash (text[m:j+1]):
                    res.add (text[i:m])
                    
        return len(res)

class Solution:
    
    def distinctEchoSubstrings2(self, text):
        base = 29
        mod = 10**9 + 7
        
        aset = set()
        n = len(text)
        
        thash = [0] * (n+1) # thash[i] is the hash value for text[0..i-1] , 从text[0]到text[i-1]都是包括的！
        tpow = [0] * (n+1) # tpow[i] = base ^ i
        tpow[0] = 1
        
        def getHash(l, r):
            return (thash[r] - thash[l]*tpow[r-l] % mod + mod) % mod # 快速获取一个区间的hash! 这个理解起来有难度！
            #       全体0..r    0..l, 幂的差r-l
        
        for i in range(1, n+1):
            #thash[i] = (thash[i-1] * base + ord(text[i-1])-ord('a')) % mod # something is wrong if we use ord(text[i-1]) - ord('a')
            thash[i] = (thash[i-1] * base + ord(text[i-1])) % mod # 简单的进位叠加，这个还算容易记住！
            tpow[i] = tpow[i-1] * base % mod # 简单的进位叠加！还算容易记住！
        
        for alen in range(1, n//2+1): # abab case? 而且代码并不直观的感觉！
            l = 0
            r = alen
            counter = 0
            while l < n - alen:
                if text[l] == text[r]:
                    counter += 1
                else:
                    counter = 0
                
                if counter == alen:
                    aset.add(getHash(l-alen+1, l+1))
                    counter -= 1
                l += 1
                r += 1
        return len(aset)
        '''public int distinctEchoSubstrings(String text) {
\t\tSet<Long> set = new HashSet<>();
\t\tint n = text.length();
\t\tpreprocess(n, text);

\t\tfor (int len = 1; len <= n / 2; len++) {
\t\t\tfor (int l = 0, r = len, counter = 0; l < n - len; l++, r++) {
\t\t\t\tif (text.charAt(l) == text.charAt(r)) {
\t\t\t\t\tcounter++;
\t\t\t\t} else {
\t\t\t\t\tcounter = 0;
\t\t\t\t}
                
                // 这个操作可以加速？！并不是所有的都是直接call getHash的！
\t\t\t\tif (counter == len) {
\t\t\t\t\tset.add(getHash(l - len + 1, l + 1));
\t\t\t\t\tcounter--;
\t\t\t\t}
\t\t\t}
\t\t}

\t\treturn set.size();
\t}'''
        
    def distinctEchoSubstrings(self, text):
        base = 29
        mod = 10**9 + 7
        aset = set()
        n = len(text)
        
        thash = [0] * (n+1)
        tpow = [0] * (n+1)
        tpow[0] = 1
        
        def getHash(l, r):
            return (thash[r] - thash[l]*tpow[r-l] % mod + mod) % mod
        for i in range(1, n+1):
            thash[i] = (thash[i-1] * base + ord(text[i-1])) % mod
            tpow[i] = tpow[i-1]*base % mod
        
        for i in range(n):
            for alen in range(2, n-i+1, 2): # i=n-1 then alen=1 is okay, i=0 then alen=n is okay; which means that i+alen=n! so alen = n - i is the upper bound
                mid = i + alen//2
                hash1 = getHash(i, mid)
                hash2 = getHash(mid, i+alen)
                if hash1 == hash2:
                    aset.add(hash1)
        return len(aset)
                

    
    def distinctEchoSubstrings1(self, text: str) -> int:
        base = 29
        mod = 10**9 + 7
        
        aset = set()
        n = len(text)
        
        thash = [0] * (n+1) # thash[i] is the hash value for text[0..i-1] , 从text[0]到text[i-1]都是包括的！
        tpow = [0] * (n+1) # tpow[i] = base ^ i
        tpow[0] = 1
        
        def getHash(l, r):
            return (thash[r] - thash[l]*tpow[r-l] % mod + mod) % mod # 快速获取一个区间的hash! 这个理解起来有难度！
            #       全体0..r    0..l, 幂的差r-l
        
        for i in range(1, n+1):
            #thash[i] = (thash[i-1] * base + ord(text[i-1])-ord('a')) % mod # something is wrong if we use ord(text[i-1]) - ord('a')
            thash[i] = (thash[i-1] * base + ord(text[i-1])) % mod # 简单的进位叠加，这个还算容易记住！
            tpow[i] = tpow[i-1] * base % mod # 简单的进位叠加！还算容易记住！
            
        # 理解一下：
        # abcd -> 
        # thash[0] = 0
        # thash[1] = (0*29 + ord('a')) % mod = ord('a') % mod
        # thash[2] = [ ord('a')*29 + ord('b') ] % mod
        # thash[3] = [ ord('a')*29*29 + ord('b') * 29 + ord('c')] % mod
        # thash[4] = [ ord('a')*29*29*29 + ord('b') * 29*29 + ord('c')*29 + ord('d')] % mod
        
        # tpow[1] = 1*29 % mod = 29 % mod
        # tpow[2] = 29*29 % mod
        # tpow[3] = 29*29*29 % mod
        # tpow[4] = 29*29*29*29 % mod
        
        # abab 的时候
        # thash[1] = [ ord('a') ] % mod
        # thash[2] = [ ord('a')*29 + ord('b') ] % mod
        # thash[3] = [ ord('a')*29*29 + ord('b') * 29 + ord('a')] % mod
        # thash[4] = [ ord('a')*29*29*29 + ord('b') * 29*29 + ord('a')*29 + ord('b')] % mod
        # tpow[4] = 29*29*29*29 % mod
        
        # i=0, alen=4 -> abab
        # mid=2
        # so, it is: 
        # getHash(0, 2) -> (ord('a')*29 + ord('b') - 0*tpow[2] + mod) % mod 
        #               -> (ord('a')*29 + ord('b') + mod) % mod
        # getHash(2, 4) -> (ord('a')*29*29*29 + ord('b') * 29*29 + ord('a')*29 + ord('b') - (ord('a')*29 + ord('b'))*29*29 + mod) % mod
        #               -> (ord('a')*29 + ord('b') + mod) % mod
        
        
        for i in range(n):
            for alen in range(2, n-i+1, 2): # 遍历所有长度为偶数的子串（中间切开，然后比较左右）
                mid = i + alen//2
                hash1 = getHash(i, mid)
                hash2 = getHash(mid, i+alen)
                if hash1 == hash2: # problem, even hash1 == hash2, not necessary mean that text[i,mid] = text[mid, i+alen]!
                    aset.add(hash1)
        return len(aset)
        
        
        '''
        class Solution {
        long BASE = 29L, MOD = 1000000007L;
        public int distinctEchoSubstrings(String str) {
            HashSet<Long> set = new HashSet<>();
            int n = str.length();
            long[] hash = new long[n + 1]; // hash[i] is hash value from str[0..i]
            long[] pow = new long[n + 1]; // pow[i] = BASE^i
            pow[0] = 1;
            for (int i = 1; i <= n; i++) {
                hash[i] = (hash[i - 1] * BASE + str.charAt(i - 1)) % MOD;
                pow[i] = pow[i - 1] * BASE % MOD;
            }
            for (int i = 0; i < n; i++) {
                for (int len = 2; i + len <= n; len += 2) {
                    int mid = i + len / 2;
                    long hash1 = getHash(i, mid, hash, pow);
                    long hash2 = getHash(mid, i + len, hash, pow);
                    if (hash1 == hash2) set.add(hash1);
                }
            }
            return set.size();
        }

        long getHash(int l, int r, long[] hash, long[] pow) {
            return (hash[r] - hash[l] * pow[r - l] % MOD + MOD) % MOD;
        }
    }
    '''

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        res = set()
        n = len(text)
        def check(s):
            l = len(s)
            if l % 2 == 0 and s[:l//2] == s[l//2:]:
                return True
            return False
        for i in range(n):
            for j in range(i+1, n+1):
                if check(text[i:j]):
                    res.add(text[i:j])
        #print(res)
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        # MOD = 10**9+7
        MOD = 2000000011
        textlen = len(text)
        half = textlen//2
        f = [[0]*textlen for i in range(textlen)]
        HASH = {}
        for l in range(1,half+1):
            HASH[l] = set()
            for i in range(textlen-l+1):
                if l == 1:
                    f[i][i+l-1] = ord(text[i])-97
                else:
                    f[i][i+l-1] = (f[i][i+l-2]*26+ord(text[i+l-1])-97)%MOD
                HASH[l].add(f[i][i+l-1])
        a = half+1 if half%2 == 1 else half+2
        for l in range(a,half*2+1,2):
            HASH[l] = set()
            for i in range(textlen-l+1):
                f[i][i+l-1]=(f[i][i+l-3]*676+(ord(text[i+l-2])-97)*26+ord(text[i+l-1])-97)%MOD
                HASH[l].add(f[i][i+l-1])
        count = 0
        # print(HASH)
        # print(f)
        tmp = 1
        for l in range(1,half+1):
            tmp = tmp*26%MOD
            for v in HASH[l]:
                if v*(tmp+1)%MOD in HASH[2*l]:
                    count += 1
        return count
                


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        echos = set()
        def find_echos(suffix):
            n = len(suffix)
            z = [0] * n
            l, r = 0, 0
            for i in range(1, n):
                if r >= i:
                    z[i] = min(r - i + 1, z[i - l])
                while i + z[i] < n and suffix[i + z[i]] == suffix[z[i]]:
                    z[i] += 1
                if i + z[i] - 1 > r:
                    l, r = i, i + z[i] - 1
            for half in range(1, 1 + (n // 2)):
                if z[half] >= half: echos.add(suffix[:2*half])
        
        for i in range(len(text) - 1):
            find_echos(text[i:])
            
        return len(echos)
        
'''

aaaaaaaaaa
2 + 4 + 6 + 


for suffix pairs
s[i:] s[j:] longest common prefix


store suffixes in a trie

..abcdabceef


abc..abc..

'''

class Solution:
    def checkValid(self, checkString):
        l = len(checkString)
        if l % 2 != 0 or l == 0:
            return False
        
        if checkString[:l//2] != checkString[l//2:]:
            return False
        return True
    
    def distinctEchoSubstrings(self, text: str) -> int:
        l = len(text)
        dic = {}
        if l == 0:
            return 0
        for start in range(l-1):    
            for end in range(l, start, -1):  
                diff = end - start
                left = text[start:diff//2 + start]
                right = text[diff//2 + start:end]
                if diff > 0 and (diff %2) == 0 and left == right:
                    dic[text[start:end]] = 1              
        return len(list(dic.keys()))

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        mod = 1_000_000_007
        hashed = {}
        for i in range(len(text)):
            sm = 0
            for j in range(i, len(text)):
                sm = (sm*128 + ord(text[j]))%mod
                hashed[(i, j)] = sm
        
        ans = 0
        st = {}
        for i in range(len(text)):
            for j in range(i+1, len(text), 2):
                if hashed[(i, i-1+(j + 1 - i)//2)] == hashed[(i+(j + 1 - i)//2, j)]:
                    if hashed[(i, j)] not in st:
                        ans += 1
                        st[hashed[(i,j)]] = 1
        return ans


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        mod = 1_000_000_007
        # Dict for storing hashes for all substrings
        hashed = {}
        for i in range(len(text)):
            sm = 0
            for j in range(i, len(text)):
                sm = (sm*128 + ord(text[j]))%mod
                hashed[(i, j)] = sm
        
        ans = 0
        st = {}
        for i in range(len(text)):
            for j in range(i+1, len(text), 2):
                # For each even length substring check if hash of first half
                # matches the hash of second half
                # Also check if the full string already exists as stored map
                if hashed[(i, i-1+(j + 1 - i)//2)] == hashed[(i+(j + 1 - i)//2, j)]:
                    if hashed[(i, j)] not in st:
                        ans += 1
                        st[hashed[(i,j)]] = 1
        return ans

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        N = len(text)
        s = set()
 
        for offset in range(1, N // 2 + 1):
            K = 0
            for j in range(N - offset):
                if text[j] == text[j+offset]:
                    K += 1
                else:
                    K = 0
                if K >= offset:
                    s.add(text[j-offset+1:j+offset+1])
        return len(s)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        mod = 1_000_000_007
        
        hashed = {}
        for i in range(len(text)):
            sm = 0
            for j in range(i, len(text)):
                sm = (sm*128 + ord(text[j]))%mod
                hashed[(i, j)] = sm
        
        ans = 0
        st = {}
        for i in range(len(text)):
            for j in range(i+1, len(text), 2):
                if hashed[(i, i-1+(j + 1 - i)//2)] == hashed[(i+(j + 1 - i)//2, j)]:
                    if hashed[(i, j)] not in st:
                        ans += 1
                        st[hashed[(i,j)]] = 1
        return ans

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        #for a in range(len(text)-1):
        #    for b in range(1, (len(text)-a)//2+1):
        #        print(text[a:a+b], text[a+b:a+2*b])
        #        if text[a:a+b]==text[a+b:a+2*b]:
        #            print('GOT ONE')
        return len({text[a:a+b] for a in range(len(text)-1) for b in range(1, (len(text)-a)//2+1) if text[a:a+b]==text[a+b:a+2*b]})


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        if len(set(text)) == 1: return len(text)//2 # 1
    
        presum = [0] # 2
        for char in text:
            presum.append(presum[-1] + ord(char))
    
        res = set()
        for w in range(1,(2 + len(text)) // 2):
            for i in range(len(text) + 1 - 2*w):
                if presum[i+w] - presum[i] == presum[i+2*w] - presum[i+w]: # 2.1
                    if text[i:i+w] == text[i+w:i+2*w]: # 3
                        res.add(text[i:i+w])
    
        return len(res)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        if len(set(text)) == 1: return len(text)//2 # 1
    
        presum = [0] # 2
        for char in text:
            presum.append(presum[-1] + ord(char))
    
        res = set()
        for w in range(1, len(text) // 2 + 1):
            for i in range(len(text) + 1 - 2*w):
                # if presum[i+w] - presum[i] == presum[i+2*w] - presum[i+w]: # 2.1
                  if text[i:i+w] == text[i+w:i+2*w]: # 3
                        res.add(text[i:i+w])
    
        return len(res)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        res = set()
        for i in range(n):
            for j in range(i):
                if text[i]==text[j] and text.startswith(text[j:i], i):
                        res.add(text[j:i])
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        ansSet = set()
        for i in range(len(text)):
            for j in range(i+1, (i+1+len(text)+1)//2):
                if text[i : j] == text[j : 2*j-i]:
                    ansSet.add(text[i : 2*j-i])
        return len(ansSet)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        N = len(text)
        BASE = 27
        MOD = 1000000007
        s = set()
        hoffset = 1
        tord = [ord(x) - ord('a') + 1 for x in text]
 
        for offset in range(1, N // 2 + 1):
            hoffset = (hoffset * BASE) % MOD
            K = 0
            h = 0
            for j in range(N - offset):
                if text[j] == text[j+offset]:
                    K += 1
                    h = (h * BASE + tord[j+offset]) % MOD
                else:
                    K = 0
                    h = 0
 
                if K > offset:
                    h = (((h - hoffset * tord[j+offset]) % MOD) + MOD) % MOD
                    K -= 1
 
                if K == offset:
                    s.add(h)
        return len(s)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        # subStrCounter = Counter()
        # subStrCounter[1] = text[0]
        # l = 0
        # r = 1
        ans = 0
        visited = set()
        textLen = len(text)
        for i in range(textLen-1):
            for j in range(0, min(i+1, textLen-i-1)):
                if text[i-j:i+1] == text[i+1:i+j+2]:
                    if text[i-j:i+1] not in visited:
                        visited.add(text[i-j:i+1])
                        ans += 1
                # if text[i-j] == text[i+j+1]:
                #     if text[i+1: i+j+2] not in visited:
                #         visited.add(text[i+1: i+j+2])
                #         ans += 1
                # else:
                #     break
        return ans

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        if n <= 1:
            return 0
        
        res = set()
        for i in range(n - 1):
            for j in range(min(i + 1, n - i - 1)):
                if text[(i-j):(i+1)] == text[(i+1):(i+j+2)]:
                    res.add(text[(i-j):(i+j+2)])
        #print(res)
        
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        res = set()
        for length in range(1, 1 + len(text)//2):
            count = 0
            l, r = 0, length
            while r < len(text):
                if text[l] == text[r]:
                    count += 1
                else:
                    count = 0
                if count == length:
                    res.add(text[l-length+1: l+1])
                    count -= 1
                l, r = l+1, r+1
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, s):
        n = len(s)
        s += '.'
        some_string = set()
        for k in range(1, n//2+1):
            same = sum(c == d for c, d in zip(s, s[k:k+k]))
            for i in range(n - 2*k + 1):
                if same == k:
                    some_string.add(s[i:i+k])
                same += (s[i+k] == s[i+k+k]) - (s[i] == s[i+k])
        return len(some_string)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        
        s = set()
        res = 0
        for i in range(0, len(text), 1):
            for j in range(i + 1, len(text), 2):
                mid = (i + j - 1) // 2
                t1 = text[i:mid+1]
                t2 = text[mid+1:j+1]
                # print(i, j, mid, t1, t2)
                
                if t1 == t2 and t1 not in s:
                    s.add(text[i:mid+1])
                    res += 1                
                    
        return len(s)
        
        
        n=len(s)
        dp=[0 for i in range(n)]
        
        dp[0]=ord(s[0])-ord('a')
        
        pw=[0]*(n+1)
        
        pw[0]=1
        
        curr=26
        
        for i in range(1,n):
            dp[i]=dp[i-1]+curr*(ord(s[i])-ord('a'))
            pw[i]=curr
            curr=curr*26
            
        pw[-1]=curr
        
        #print(dp)
        
        st=set()
        
        for i in range(n):
            for j in range(i+1,n,2):
                
                mid=(j+i)//2
                
                if i!=0:
                    x1=dp[mid]-dp[i-1]
                else:
                    x1=dp[mid]
                
                x2=dp[j]-dp[mid]
                
                #print(x1,x2,s[i:mid+1],s[mid+1:j+1])
                
                if x2==x1*(pw[mid-i+1]):
                    if s[i:mid+1]==s[mid+1:j+1]:
                        st.add(s[i:j+1])
                        #print(st)
        return len(st) 

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        s =text
        n = len(s)
        s += '.'
        some_string = set()
        for k in range(1, n//2+1):
            same = sum(c == d for c, d in zip(s, s[k:k+k]))
            for i in range(n - 2*k + 1):
                if same == k:
                    some_string.add(s[i:i+k])
                same += (s[i+k] == s[i+k+k]) - (s[i] == s[i+k])
        return len(some_string)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        text += '.'
        seen = set()
        for k in range(1, n // 2 + 1):
            same = sum(c == d for c, d in zip(text, text[k: k + k]))
            for i in range(n - 2 * k + 1):
                if same == k:
                    seen.add(text[i: i + k])
                same += (text[i + k] == text[i + k * 2]) - (text[i] == text[i + k])
        return len(seen)
        # n = len(text)
        # seen = set()
        # for i in range(n):
        #     for j in range(i + 1, n + 1):
        #         if not (j - i) % 2 and text[i: i + (j - i) // 2] == text[i + (j - i) // 2: j]:
        #             seen.add(text[i: j])
        # return len(seen)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:

        if len(set(text)) == 1: return len(text)//2 # 1

        presum = [0] # 2
        for char in text:
            presum.append(presum[-1] + ord(char))

        res = set()
        for w in range(1,(2 + len(text)) // 2):
            for i in range(len(text) + 1 - 2*w):
                j = i + w
                if presum[j] - presum[i] == presum[j+w] - presum[j]: # 2.1
                    if text[i:j] == text[j:j+w]: # 3
                        res.add(text[i:j])

        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        # stefan++
        N = len(text)
        res = set()
        text += '.'
        # k is the length of substring
        for k in range(1, N//2 + 1):
            same = sum(a == b for a, b in zip(text, text[k:k+k]))
            for i in range(N - 2*k + 1):
                if same == k:
                    res.add(text[i:i+k])
                same += (text[i+k] == text[i+ 2*k]) - (text[i] == text[i + k])
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        text+='*'
        valid = set()
        for k in range(1, n//2 +1):
            same = sum(c==d for c,d in zip(text, text[k:k+k]))
            for i in range(n-2*k+1):
                if same==k:
                    valid.add(text[i:i+k])
                same+= (text[i+k]==text[i+k+k]) -(text[i]==text[i+k])
        return len(valid)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        # not the rolling hash method
        # optimize
        resultset = set()
        
        for i in range(len(text)):
            for j in range(i+1, len(text)):
                
                if text[i] == text[j]:
                    #compare two sliced string
                    str1 = text[i:j]
                    str2 = text[j: j+(j-i)]
                                       
                    if str1 == str2:
                        resultset.add(text[i: j+(j-i)])

        return len(resultset)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        L = len(text)
        
        count = 0
        S = set()
        
        for i in range(L):
            for j in range(i+1, L):
                
                if j - i <= L - j:
                    
                    #print(text[i:j])
                    #print(text[j:2*j-i])
                    
                    if text[i:j] == text[j:2*j-i]:
                        #print('here')
                        
                        S.add(text[i:j])
                        
                        #if text[i:j] not in D:
                        #    D[text[i:j]] = 1
                        #    count += 1
                    
        return len(S)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        satisfies = set()
        for i in range(2,len(text)+2,2):
            for j in range(0,len(text)-i+1):
                cand = text[j:j+i]
                if cand[:len(cand)//2] == cand[len(cand)//2:]:
                    satisfies.add(cand)
        return len(satisfies)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        res = set()
        n = len(text)
        for sz in range(1,int(n/2)+1,1):
            r = sz
            cur = 0
            for l in range(0,n-sz):
                if text[l] == text[r]:
                    cur += 1
                else:
                    cur = 0
                if cur == sz:
                    #print('size: ' + str(sz) + ' L: ' + str(l) + text[l-sz:l])
                    res.add(text[l-sz+1:l+1])
                    cur -= 1
                r += 1
        return len(res)


class Solution:
  def distinctEchoSubstrings(self, text: str) -> int:
    # O(N^2) check all substr, O(1) each check with rolling count of equality
    # s: text + '#' in case length of text is odd and out of index error
    s, n = text + '#', len(text)
    echo = set()
    for k in range(1, n // 2 + 1):
      # init
      same = sum(x == y for x, y in zip(s[:k], s[k:(k + k)]))
      for i in range(n - 2 * k + 1):
        if same == k:
          echo.add(s[i:(i + 2 * k)])
        # rolling the count of equality
        same += (s[i + k] == s[i + k + k]) - (s[i] == s[i + k])
    return len(echo)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        N = len(text)
        BASE = 27
        MOD = 1000000007
        s = set()
        hoffset = 1
        tord = [ord(x) - ord('a') + 1 for x in text]
 
        for offset in range(1, N // 2 + 1):
            hoffset = (hoffset * BASE) % MOD
            K = 0
            h = 0
            for j in range(N - offset):
                if text[j] == text[j+offset]:
                    K += 1
                    h = (h * BASE + tord[j+offset]) % MOD
                else:
                    K = 0
                    h = 0
 
                if K > offset:
                    h = (((h - hoffset * tord[j+offset]) % MOD) + MOD) % MOD
                    K -= 1
 
                if K == offset:
                    s.add(h)
        return len(s)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n=len(text)
        res=set()
        for k in range(1,n//2+1):
            for i in range(n-k+1):
                if text[i:i+k]==text[i+k:i+2*k]:
                    res.add(text[i:i+2*k])
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        result = set()
        size = len(text)
        for i in range(size):
            for j in range(i+1, size):
                if text[i:j] == text[j:j+(j-i)]:
                    result.add(text[i:j])
                
        return len(result)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        res = set()
        n = len(text)
        for sz in range(1,int(n/2)+1):
            r = sz
            cur = 0
            for l in range(0,n-sz):
                if text[l] == text[r]:
                    cur += 1
                else:
                    cur = 0
                if cur == sz:
                    #print(text[l-sz+1:l+1])
                    res.add(text[l-sz+1:l+1])
                    cur -= 1
                r += 1
        return len(res)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        result = set()
        size = len(text)
        for i in range(size):
            for j in range(i+1, size):
                if text[i:j] == text[j:j+(j-i)]:
                    result.add(text[i:j])
            
        print(result)
        return len(result)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        distinct_subs = set()
        for i in range(2, len(text)+1, 2):
            for j in range(len(text)+1-i):
                sub_string = text[j:j+i]
                if sub_string[:int(i/2)] == sub_string[int(i/2):]:
                    if sub_string not in distinct_subs:
                        distinct_subs.add(sub_string)
        
        return len(distinct_subs)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n, size, res = len(text), 1, set()
        while size * 2 <= n:
            count = 0
            for i in range(size):
                if text[i] == text[i + size]:
                    count += 1
            for j in range(n - 2 * size + 1):
                if count == size:
                    res.add(text[j : j + 2 * size])
                if text[j] == text[j + size]:
                    count -= 1
                if j + 2 * size < n and text[j + size] == text[j + 2 * size]:
                    count += 1
            size += 1
        
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        L = len(text)
        res = set()
        for i in range(1, L):
            for j in range(max(0, 2*i-L), i):
                if text[j:i] == text[i:2*i-j]:
                    res.add(text[j:i])
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        some_strings = set()
        for i in range(len(text)):
            for j in range (i):
                if text.startswith(text[j:i],i):
                    some_strings.add(text[j:i])
        return len(some_strings)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        
        d = set()
        c = 0
        lim = len(text)
        
        for i in range(0,lim,2):
            for j in range(0,lim-i):
                val = text[j:j+i]
                if val not in d:
                    d.add(val)
                    if 2*val[:i//2]==val:c+=1
        if 2*text[:lim//2]==text:c+=1        
        return c-1

class Solution:
    def distinctEchoSubstrings3(self, text: str) -> int:
        if len(set(text)) == 1: return len(text)//2 # 1

        presum = [0] # 2
        for char in text:
            presum.append(presum[-1] + ord(char))
        print(presum)

        res = set()
        for w in range(1,(2 + len(text)) // 2):
            for i in range(len(text) + 1 - 2*w):
                if presum[i+w] - presum[i] == presum[i+2*w] - presum[i+w]: # 2.1
                    if text[i:i+w] == text[i+w:i+2*w]: # 3
                        res.add(text[i:i+w])

        return len(res)

    def distinctEchoSubstrings(self, text: str) -> int:
        result = set()
        size = len(text)
        presum = [0] * size * 2
        
        for i in range(size):        
            presum[i] = presum[i-1] + ord(text[i])
        for i in range(size):
            for j in range(i+1, size):
                if presum[j-1]-presum[i] == presum[j+(j-i)-1]-presum[j]:
                    if text[i:j] == text[j:j+(j-i)]:
                        result.add(text[i:j])
            
        print(result)
        return len(result)

class Solution:
  def distinctEchoSubstrings(self, s: str) -> int:
    n, seen = len(s), set()
    for i in range(n):
      for j in range(i + 2, n + 1, 2):
        tmp = s[i:j]
        l = (j - i) // 2
        if tmp[:l] == tmp[l:]:
          seen.add(tmp[:l])
    
    return len(seen)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        result = set()
        size = len(text)
        presum = [0] * size * 2
        
        for i in range(size):        
            presum[i] = presum[i-1] + ord(text[i])
        for i in range(size):
            for j in range(i+1, size):
                if presum[j-1]-presum[i] == presum[j+(j-i)-1]-presum[j]:
                    if text[i:j] == text[j:j+(j-i)]:
                        result.add(text[i:j])
            
        print(result)
        return len(result)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        l = len(text)
        dic = {}
        if l == 0:
            return 0
        for start in range(l-1):    
            for end in range(l, start, -1):  
                diff = end - start
                if (diff %2) == 0 and text[start:diff//2 + start] == text[diff//2 + start:end]:
                    dic[text[start:end]] = 1              
        return len(list(dic.keys()))


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        l = len(text)
        dic = {}
        if l == 0:
            return 0
        for start in range(l-1):    
            for end in range(l, start, -1):  
                diff = end - start
                if (diff %2) == 0 and text[start:diff//2 + start] == text[diff//2 + start:end]:
                    dic[text[start:end]] = 1              
        return len(list(dic.keys()))

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        seen = set()
        for i in range(n):
            for j in range(i + 1, n + 1):
                if not (j - i) % 2 and text[i: i + (j - i) // 2] == text[i + (j - i) // 2: j]:
                    seen.add(text[i: j])
        return len(seen)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        s=set()
        for j in range(len(text)):
            for i in range(j):
                #print(text[i:j])
                if text[i:j]==text[j:j+j-i]:
                    s.add(text[i:j])
                #print(s)
        return len(s)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        res = set()                                           # keep distinct
        for i in range(len(text)):                            # i: start index
            for l in range(1,len(text)-i):                    # l: length of the repeated string
                if text[i] == text[i+l]:                      # only check if the first character matches
                    k = 1                                     # k: repeated times
                    while i+(k+1)*l <= len(text):
                        if text[i:i+k*l] == text[i+k*l:i+(k+1)*l]:
                            res.add(text[i:i+(k+1)*l])
                            k *= 2                            # double the count and continue checking
                        else:
                            break
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:

        if len(set(text)) == 1: return len(text)//2 # 1

        presum = [0] # 2
        for char in text:
            presum.append(presum[-1] + ord(char))

        res = set()
        for w in range(1,(2 + len(text)) // 2):
            for i in range(len(text) + 1 - 2*w):
                if presum[i+w] - presum[i] == presum[i+2*w] - presum[i+w]: # 2.1
                    if text[i:i+w] == text[i+w:i+2*w]: # 3
                        res.add(text[i:i+w])

        return len(res)

class Solution:
    
    def distinctEchoSubstrings(self, text: str) -> int:
        l = len(text)
        dic = {}
        if l == 0:
            return 0
        for start in range(l-1):    
            for end in range(l, start, -1):  
                diff = end - start
                if diff > 0 and (diff %2) == 0 and text[start:diff//2 + start] == text[diff//2 + start:end]:
                    dic[text[start:end]] = 1              
        return len(list(dic.keys()))

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
      result = set()
      for j in range(3, len(text) + 1):
        for i in range(0, j):
          if (j - i) & 1 > 0: 
            continue
          if self.check(text[i: j]):
            result.add(text[i: j])
      return len(result)
    
    def check(self, text: str) -> bool:
      mid = len(text) >> 1
      return text[:mid] == text[mid:]


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        prefix_rolling_hash = [0 for _ in range(len(text) + 1)]
        for i in range(len(text)):
            prefix_rolling_hash[i + 1] = ord(text[i]) + prefix_rolling_hash[i]
        res = set()
        for i in range(len(text)):
            for j in range(i):
                if (i - j + 1) % 2 == 0:
                    if prefix_rolling_hash[j + ((i - j + 1) // 2)] - prefix_rolling_hash[j] == prefix_rolling_hash[i + 1] - prefix_rolling_hash[j + ((i - j + 1) // 2)]:
                        x = text[j: (j + (i - j + 1) // 2)]
                        if x == text[(j + (i - j + 1) // 2): i + 1]:
                            res.add(x)
        return len(res)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        st = set()
        for s in range(1, 1 + len(text) // 2):
            for start in range(len(text)):
                l = text[start:start+s]
                r = text[start+s:start+s+s]
                if l == r and (l+r) not in st and len(l) != 0:
                    st.add(l+r)
        return len(st)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        ans = set([])
        for i in range(n):
            pat = text[i:]
            lps = [0]*(n-i)
            j = 1
            k = 0
            while j<len(lps):
                if pat[j]==pat[k]:
                    k+=1
                    lps[j]=k
                    j+=1
                    d = j-k
                    if j%d==0 and (j//d)%2==0:
                        ans.add(pat[:j])
                else:
                    if k!=0:
                        k = lps[k-1]
                    else:
                        lps[j]=0
                        j+=1
            
        return len(ans)
                            


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        subs=set()
    
        for i in range(len(text)):
            for j in range(i+1,len(text)):
            
                temp=text[i:j]
                if text[i:j]==text[j:j+j-i] :
                    subs.add(text[i:j])
            
    #print(subs)
        return len(subs)

class Solution:
    
    def distinctEchoSubstrings(self, text):
        base = 29
        mod = 10**9 + 7
        
        aset = set()
        n = len(text)
        
        thash = [0] * (n+1) # thash[i] is the hash value for text[0..i-1] , 从text[0]到text[i-1]都是包括的！
        tpow = [0] * (n+1) # tpow[i] = base ^ i
        tpow[0] = 1
        
        def getHash(l, r):
            return (thash[r] - thash[l]*tpow[r-l] % mod + mod) % mod # 快速获取一个区间的hash! 这个理解起来有难度！
            #       全体0..r    0..l, 幂的差r-l
        
        for i in range(1, n+1):
            #thash[i] = (thash[i-1] * base + ord(text[i-1])-ord('a')) % mod # something is wrong if we use ord(text[i-1]) - ord('a')
            thash[i] = (thash[i-1] * base + ord(text[i-1])) % mod # 简单的进位叠加，这个还算容易记住！
            tpow[i] = tpow[i-1] * base % mod # 简单的进位叠加！还算容易记住！
        
        for alen in range(1, n//2+1): # abab case?
            l = 0
            r = alen
            counter = 0
            while l < n - alen:
                if text[l] == text[r]:
                    counter += 1
                else:
                    counter = 0
                
                if counter == alen:
                    aset.add(getHash(l-alen+1, l+1))
                    counter -= 1
                l += 1
                r += 1
        return len(aset)
        '''public int distinctEchoSubstrings(String text) {
\t\tSet<Long> set = new HashSet<>();
\t\tint n = text.length();
\t\tpreprocess(n, text);

\t\tfor (int len = 1; len <= n / 2; len++) {
\t\t\tfor (int l = 0, r = len, counter = 0; l < n - len; l++, r++) {
\t\t\t\tif (text.charAt(l) == text.charAt(r)) {
\t\t\t\t\tcounter++;
\t\t\t\t} else {
\t\t\t\t\tcounter = 0;
\t\t\t\t}
                
                // 这个操作可以加速？！并不是所有的都是直接call getHash的！
\t\t\t\tif (counter == len) {
\t\t\t\t\tset.add(getHash(l - len + 1, l + 1));
\t\t\t\t\tcounter--;
\t\t\t\t}
\t\t\t}
\t\t}

\t\treturn set.size();
\t}'''

    
    def distinctEchoSubstrings1(self, text: str) -> int:
        base = 29
        mod = 10**9 + 7
        
        aset = set()
        n = len(text)
        
        thash = [0] * (n+1) # thash[i] is the hash value for text[0..i-1] , 从text[0]到text[i-1]都是包括的！
        tpow = [0] * (n+1) # tpow[i] = base ^ i
        tpow[0] = 1
        
        def getHash(l, r):
            return (thash[r] - thash[l]*tpow[r-l] % mod + mod) % mod # 快速获取一个区间的hash! 这个理解起来有难度！
            #       全体0..r    0..l, 幂的差r-l
        
        for i in range(1, n+1):
            #thash[i] = (thash[i-1] * base + ord(text[i-1])-ord('a')) % mod # something is wrong if we use ord(text[i-1]) - ord('a')
            thash[i] = (thash[i-1] * base + ord(text[i-1])) % mod # 简单的进位叠加，这个还算容易记住！
            tpow[i] = tpow[i-1] * base % mod # 简单的进位叠加！还算容易记住！
            
        # 理解一下：
        # abcd -> 
        # thash[0] = 0
        # thash[1] = (0*29 + ord('a')) % mod = ord('a') % mod
        # thash[2] = [ ord('a')*29 + ord('b') ] % mod
        # thash[3] = [ ord('a')*29*29 + ord('b') * 29 + ord('c')] % mod
        # thash[4] = [ ord('a')*29*29*29 + ord('b') * 29*29 + ord('c')*29 + ord('d')] % mod
        
        # tpow[1] = 1*29 % mod = 29 % mod
        # tpow[2] = 29*29 % mod
        # tpow[3] = 29*29*29 % mod
        # tpow[4] = 29*29*29*29 % mod
        
        # abab 的时候
        # thash[1] = [ ord('a') ] % mod
        # thash[2] = [ ord('a')*29 + ord('b') ] % mod
        # thash[3] = [ ord('a')*29*29 + ord('b') * 29 + ord('a')] % mod
        # thash[4] = [ ord('a')*29*29*29 + ord('b') * 29*29 + ord('a')*29 + ord('b')] % mod
        # tpow[4] = 29*29*29*29 % mod
        
        # i=0, alen=4 -> abab
        # mid=2
        # so, it is: 
        # getHash(0, 2) -> (ord('a')*29 + ord('b') - 0*tpow[2] + mod) % mod 
        #               -> (ord('a')*29 + ord('b') + mod) % mod
        # getHash(2, 4) -> (ord('a')*29*29*29 + ord('b') * 29*29 + ord('a')*29 + ord('b') - (ord('a')*29 + ord('b'))*29*29 + mod) % mod
        #               -> (ord('a')*29 + ord('b') + mod) % mod
        
        
        for i in range(n):
            for alen in range(2, n-i+1, 2): # 遍历所有长度为偶数的子串（中间切开，然后比较左右）
                mid = i + alen//2
                hash1 = getHash(i, mid)
                hash2 = getHash(mid, i+alen)
                if hash1 == hash2: # problem, even hash1 == hash2, not necessary mean that text[i,mid] = text[mid, i+alen]!
                    aset.add(hash1)
        return len(aset)
        
        
        '''
        class Solution {
        long BASE = 29L, MOD = 1000000007L;
        public int distinctEchoSubstrings(String str) {
            HashSet<Long> set = new HashSet<>();
            int n = str.length();
            long[] hash = new long[n + 1]; // hash[i] is hash value from str[0..i]
            long[] pow = new long[n + 1]; // pow[i] = BASE^i
            pow[0] = 1;
            for (int i = 1; i <= n; i++) {
                hash[i] = (hash[i - 1] * BASE + str.charAt(i - 1)) % MOD;
                pow[i] = pow[i - 1] * BASE % MOD;
            }
            for (int i = 0; i < n; i++) {
                for (int len = 2; i + len <= n; len += 2) {
                    int mid = i + len / 2;
                    long hash1 = getHash(i, mid, hash, pow);
                    long hash2 = getHash(mid, i + len, hash, pow);
                    if (hash1 == hash2) set.add(hash1);
                }
            }
            return set.size();
        }

        long getHash(int l, int r, long[] hash, long[] pow) {
            return (hash[r] - hash[l] * pow[r - l] % MOD + MOD) % MOD;
        }
    }
    '''

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        if len(set(text)) == 1: return len(text)//2 # 1
    
        presum = [0] # 2
        for char in text:
            presum.append(presum[-1] + ord(char))
    
        res = set()
        for w in range(1, len(text) // 2 + 1):
            for i in range(len(text) + 1 - 2*w):
                if presum[i+w] - presum[i] == presum[i+2*w] - presum[i+w]: # 2.1
                    if text[i:i+w] == text[i+w:i+2*w]: # 3
                        res.add(text[i:i+w])
    
        return len(res)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        def check(s):return s[:len(s)//2]==s[len(s)//2:]
        ret = set()
        n = len(text)
        for l in range(2,n+1,2):
            for start in range(n-l+1):
                s=text[start:start+l]
                if check(text[start:start+l]): ret.add(s)
        # print(ret)
        return len(ret)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        result = 0
        string_set = set()
        n = len(text)
        for i in range(n):
            for j in range(i+1, n+1):
                if (j-i)%2:
                    continue
                s0 = text[i:j]
                if s0 in string_set:
                    continue
                # print(text[i:j])
                string_set.add(s0)
                s1 = text[i:i+(j-i)//2]
                s2 = text[i+(j-i)//2:j]
                if s1==s2:
                    result += 1
        return result

class Solution:
    def checkSymetric(self, checkString):
        l = len(checkString)
        if l % 2 != 0 or l == 0:
            return False
        
        if checkString[:l//2] != checkString[l//2:]:
            return False
        return True
    
    def distinctEchoSubstrings(self, text: str) -> int:
        l = len(text)
        dic = {}
        for start in range(l):    
            for end in range(l, start, -1):  
                if (end - start) %2 == 0:
                    if (self.checkSymetric(text[start:end])):
                        dic[text[start:end]] = 1              
        return len(list(dic.keys()))

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        result = 0
        string_set = set()
        n = len(text)
        for i in range(n):
            for j in range(i+1, n+1):
                if (j-i)%2:
                    continue
                if text[i:j] in string_set:
                    continue
                # print(text[i:j])
                string_set.add(text[i:j])
                s1 = text[i:i+(j-i)//2]
                s2 = text[i+(j-i)//2:j]
                if s1==s2:
                    result += 1
        return result

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n=len(text)
        ans=set()
        lens=n
        for l in range(1,lens+1):
            for i in range(lens-l+1):
                j=i+l-1
                # print(i,j)
                curr1=text[i:j+1]
                # print(curr1)
                curr2=''
                if(j+l+1<=n):
                    curr2=text[j+1:j+1+l]
                if(curr1==curr2):
                    ans.add(curr1+curr2)
        return len(ans)
                


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        res = set()
        n = len(text)
        def check(s):
            l = len(s)
            if l % 2 == 0 and s[:l//2] == s[l//2:]:
                return True
            return False
        for i in range(n):
            for j in range(i+1, n+1):
                if check(text[i:j]):
                    res.add(text[i:j])
        #print(res)
        return len(res)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        
        subs=set()
        
        for i in range(len(text)):
            for j in range(i+1,len(text)):
                
                temp=text[i:j]
                
                #print(\"\\t\\t temp:\",temp,\"\\t\\t \",temp==text.startswith(temp,j))
                if text[i:j]==text[j:j+j-i] :#text.startswith(text[i:j],j):
                    subs.add(text[i:j])
                
        #print(subs)
        return len(subs)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        # 1. Use two pointers, start with 2 pointers that are 1 space apart
        # 2. Then space the pointers 2, 3, 4 up to len(text)//2
        # 3. Run the pointers along the text and anytime text[i] == text[j]
        #    expand until i reaches where j started or text[i] != text[j]
        #
        #    Optimization, rabin-karp hash the entire text and check if len(i+window)-i == len(j+window) - j
        
        if len(set(text)) == 1: return len(text)//2
        
        rabin = [0]
        for char in text:
            rabin.append(rabin[-1] + ord(char))
        
        #print(rabin)
        res = set()
        for w in range(1,(2 + len(text)) // 2):
            i = 0
            j = w
            while j <= len(text) - w:
                if rabin[j] - rabin[i] == rabin[j+w] - rabin[j]:
                    #print(text[i:j], rabin[j] - rabin[i], rabin[j+w] - rabin[j])
                    if text[i:j] == text[j:j+w]:
                        res.add(text[i:j])
                i += 1
                j += 1
        return len(res)

class Solution:
    # O(n^3) time, O(n^2) space
    def distinctEchoSubstrings(self, text: str) -> int:
        
        def is_echo(s):
            n = len(s)
            if n % 2 != 0:
                return False
            return s[: n // 2] == s[n // 2 :]
        
        echo_str_set = set()
        for i in range(len(text)):
            for j in range(i, len(text)):
                substr = text[i : j + 1]
                if is_echo(substr):
                    echo_str_set.add(substr)
        return len(echo_str_set)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        nums = [ord(c) - ord('a') for c in text]
        
        def countEcho(L):
            '''
            count echo substrings with length L
            '''
            
            a = 26
            modulus = 2**32
            
            h1 = h2 = 0
            for i in range(L):
                h1 = (h1*a + nums[i]) % modulus
                h2 = (h2*a + nums[L+i]) % modulus
            # print(L, h1, h2)
            seen = set()
            ans = 0
            if h1 == h2:
                ans += 1
                seen.add(h1)
            aL = pow(a, L, modulus)
            for i in range(1, n - 2*L + 1):
                h1 = (h1 * a - nums[i-1] * aL + nums[i+L-1]) % modulus
                h2 = (h2 * a - nums[i+L-1] * aL + nums[i+L*2-1]) % modulus
                # print(L, h1, h2)
                if h1 == h2 and h1 not in seen:
                    ans += 1
                    seen.add(h1)
            return ans
        
        ans = 0
        for L in range(1, n//2+1):
            al = countEcho(L)
            ans += al
        return ans

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        variants = [text[x:y] for x, y in itertools.combinations(range(len(text) + 1), r=2) if y - x > 1 and (y - x) % 2 == 0 and (size := (y - x) // 2) > 0 and text[x:x + size] == text[x + size:y]]
        return len(set(variants))

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n=len(text)
        ans=set()
        i=0
        while i<n:
            for l in range(2,n+1,2):
                mid=i+l//2
                if text[i:mid]==text[mid:i+l]:
                    ans.add(text[i:mid])
                l+=2
            i+=1
        return len(ans)

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        '''
        ccbccbcabc
        Input: text = \"abcabcabc\"
        Output: 3
        Explanation: The 3 substrings are \"abcabc\", \"bcabca\" and \"cabcab\".
        
        def EchoLen(i,j): length of echo string xxxi,xxxj
            if i<0: return 0
            if i == j: return 0
            if text[i] == text[j]:
                res = 1+EchoLen(i-1,-1j)
            else: 
                res = 0
        
        
        if text[i] == text[j]:
            dp[i][j] = dp[i-1][j-1]+1
        else: dp[i][j] = 0
        
        
        '''
        res = set()
        dp = [[0 for _ in range(len(text))] for _ in range(len(text))]
        for i in range(len(text)):
            for j in range(i+1,len(text)):
                if i == 0:
                    if text[i] == text[j]:
                        dp[i][j] = 1
                else:
                    if text[i] == text[j]:
                        dp[i][j] = 1+dp[i-1][j-1]
        # print(dp)
        for i in range(len(text)):
            for j in range(i+1,len(text)):
                if (j-i+1)%2==0:
                    m = (i+j)//2
                    if dp[m][j]>=(j-m): 
                        # print(i,j,m)
                        res.add(text[i:m+1])
        print(res)
        return len(res)
                    


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        result = 0
        seen = set()
        BASE = 27
        MOD = 10 ** 9
        hashs = [0] * (n + 1)
        pows = [1] * (n + 1)
        for i in range(n):
            hashs[i + 1] = (hashs[i] * BASE + ord(text[i]) - 96) % MOD
            pows[i + 1] = (pows[i] * BASE) % MOD
            
        h = lambda i, j: (hashs[j + 1] - (hashs[i] * pows[j - i + 1]) % MOD) % MOD
        
        for i in range(n):
            l = i
            r = i + 1
            while r < n:
                h1 = h(i, l)
                h2 = h(l + 1, r)
                if h1 == h2 and h1 not in seen:
                    result += 1
                    seen.add(h1)
                l += 1
                r += 2
        return result

class Solution:
    def checkSymetric(self, checkString):
        l = len(checkString)
        if l % 2 != 0 or l == 0:
            return False
        
        if checkString[:l//2] != checkString[l//2:]:
            return False
        return True
    
    def distinctEchoSubstrings(self, text: str) -> int:
        l = len(text)
        dic = {}
        for start in range(l):    
            for end in range(l, start, -1):  
                if (self.checkSymetric(text[start:end])):
                    dic[text[start:end]] = 1              
        return len(list(dic.keys()))

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        st = set()
        for s in range(1, 1 + len(text) // 2):
            for start in range(len(text)):
                l = text[start:start+s]
                r = text[start+s:start+s+s]
                if l == r and (l+r) not in st and len(l) != 0:
                    st.add(l+r)
        return len(st)


class Solution:
    def distinctEchoSubstrings(self, s):
        n = len(s)
        shash = [0] * (n + 1)
        spow = [1] * (n + 1)
        base = 29
        MOD = 10 ** 9 + 7
        seen = set()
        
        def gethash(i: int, j: int) -> int:
            return (shash[j] - shash[i - 1] * spow[j - i + 1] % MOD + MOD) % MOD
        
        for i in range(1, n + 1):
            shash[i] = (shash[i - 1] * base + ord(s[i - 1])) % MOD
            spow[i] = (spow[i - 1] * base) % MOD
        
        for i in range(n):
            for j in range(i + 1, n, 2):
                mid = (i + j) // 2
                lhash = gethash(i + 1, mid + 1)
                rhash = gethash(mid + 2, j + 1)
                if lhash == rhash:
                    #print(s[i - 1:j], lhash)
                    seen.add(lhash)
        
        return len(seen)
    
    
    # [0, 108, 3233, 93858, 2721998, 78938041, 289203286, 386895338, 219964826, 378980020, 990420611, 722197624, 943731072, 368200998, 677828983, 657040474, 54173714]
    


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        out = set()
        for i in range(len(text)-1):
            for j in range(i+1,len(text)):
                if text[i:j]==text[j:2*j -i]:
                    out.add(text[i:j])
        return len(out)


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)
        result = 0
        seen = set()
        BASE = 27
        MOD = 10 ** 5
        hashs = [0] * (n + 1)
        pows = [1] * (n + 1)
        for i in range(n):
            hashs[i + 1] = (hashs[i] * BASE + ord(text[i]) - 96) % MOD
            pows[i + 1] = (pows[i] * BASE) % MOD
            
        h = lambda i, j: (hashs[j + 1] - (hashs[i] * pows[j - i + 1]) % MOD) % MOD
        
        for i in range(n):
            l = i
            r = i + 1
            while r < n:
                h1 = h(i, l)
                h2 = h(l + 1, r)
                s = text[i: l + 1]
                if h1 == h2 and s == text[l + 1: r + 1] and s not in seen:
                    result += 1
                    seen.add(s)
                l += 1
                r += 2
        return result

class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        n = len(text)

        MOD = 10**9+7
        BASE = 256
        
        ppow = defaultdict(int)
        ippow = defaultdict(int)
        ha = defaultdict(int)
        vis = defaultdict(bool)
        
        
        ippow[0] = ppow[0] = 1
        for i in range(n):
            ha[i] = (ha[i-1] + ord(text[i]) * ppow[i]) % MOD
            ppow[i+1] = ppow[i] * BASE % MOD
            ippow[i+1] = pow(ppow[i+1], -1, MOD)
        
        def compute(i, j):
            return (ha[j] - ha[i-1]) * ippow[i] % MOD
        
        ret = 0
        for i in range(n):
            for j in range(i,n):
                if j+j-i+1 < n:
                    c1 = compute(i, j)
                    if vis[c1]:
                        continue
                    u = j+1
                    v = j+j-i+1
                    if c1 == compute(u, v) and text[i:j+1] == text[u:v+1]:
                        vis[c1] = True
                        ret += 1
        
        return ret
        
            


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        count = 0
        visited = {}
        for i in range(len(text)):
            for length in range(1, len(text)//2+1):
                now = text[i:i+length] 
                if now in visited:
                    continue
                    
                if now  == text[i+length:i + 2*length]:
                    count += 1
                    visited[now] = 1
        
        return count
                    


class Solution:
    def distinctEchoSubstrings(self, text: str) -> int:
        
        
        seen = set()        
        count = 0
        
        for i in range(len(text)-1):
            for j in range(i, len(text), 1):
                l=(j-i+1)//2
                if l<1: continue
                h=l+i
                t = text[i:h+l]
                
                # print(text[i:h], text[h:h+l], i, j)
                if t in seen: continue
                
                if t[:l] == t[l:]:
                    count += 1
                    # print( '**', text[i:h+l])
                    seen.add(t)
                    
                    
        return count