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: MEDIUM
Tags: String algorithms

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

Solutions:
from collections import defaultdict, deque

class Solution:

	def distinctEchoSubstrings(self, text: str) -> int:
		if all((x == text[0] for x in text)):
			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
				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):
				l = (j - i + 1) // 2
				h = l + i
				if l < 1 or text[i:h + l] in seen:
					continue
				if text[i:h] == text[h:h + l]:
					count += 1
					seen.add(text[i:h + l])
		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)
		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 alen in range(1, n // 2 + 1):
			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)

	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):
				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)
		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):
				mid = i + alen // 2
				hash1 = getHash(i, mid)
				hash2 = getHash(mid, i + alen)
				if hash1 == hash2:
					aset.add(hash1)
		return len(aset)


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])
		return len(res)


class Solution:

	def distinctEchoSubstrings(self, text: str) -> int:
		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
		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)


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 = 1000000007
		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:
		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:
		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
		presum = [0]
		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]:
					if text[i:i + w] == text[i + w:i + 2 * w]:
						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:
		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:
		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
		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])
		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]
				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
		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]
				if x2 == x1 * pw[mid - i + 1]:
					if s[i:mid + 1] == s[mid + 1:j + 1]:
						st.add(s[i:j + 1])
		return len(st)


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)


class Solution:

	def distinctEchoSubstrings(self, text: str) -> int:
		N = len(text)
		res = set()
		text += '.'
		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:
		resultset = set()
		for i in range(len(text)):
			for j in range(i + 1, len(text)):
				if text[i] == text[j]:
					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:
					if text[i:j] == text[j:2 * j - i]:
						S.add(text[i:j])
		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:
					res.add(text[l - sz + 1:l + 1])
					cur -= 1
				r += 1
		return len(res)


class Solution:

	def distinctEchoSubstrings(self, text: str) -> int:
		(s, n) = (text + '#', len(text))
		echo = set()
		for k in range(1, n // 2 + 1):
			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])
				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)
		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:
		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
		presum = [0]
		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]:
					if text[i:i + w] == text[i + w:i + 2 * w]:
						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:
		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:
		res = set()
		for i in range(len(text)):
			for l in range(1, len(text) - i):
				if text[i] == text[i + l]:
					k = 1
					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
						else:
							break
		return len(res)


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])
				elif 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])
		return len(subs)


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)
		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
				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:
		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
				curr1 = text[i:j + 1]
				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:

		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):
			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
			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
				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:
		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
				elif text[i] == text[j]:
					dp[i][j] = 1 + dp[i - 1][j - 1]
		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:
						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 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:
					seen.add(lhash)
		return len(seen)


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