Given a string s, the task is to check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.  
Example 1:
Input: s = "ababab"
Output: 1
Explanation: It is contructed by 
appending "ab" 3 times
Example 2:
Input: s = "ababac"
Output: 0
Explanation: Not possible to construct
User Task:
Your task is to complete the function isRepeat() which takes a single string as input and returns 1 if possible to construct, otherwise 0. You do not need to take any input or print anything.
Expected Time Complexity: O(|s|)
Expected Auxiliary Space: O(|s|)
Constraints:
1 <= |s| <= 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: String algorithms

Data structures

Starter code: #User function Template for python3

class Solution:

	def isRepeat(self, s):

		# code here

Solutions:
class Solution:

	def isRepeat(self, s):
		n = len(s)
		for i in range(1, n // 2 + 1):
			if n % i == 0:
				s1 = s[:i]
				if s1 * (n // i) == s:
					return 1
		return 0


class Solution:

	def isRepeat(self, s):
		l = len(s)
		if l <= 1:
			return 0
		i = l // 2
		j = 0
		while j < i:
			if s[:j + 1] * (l // (j + 1)) == s:
				return 1
			j += 1
		return 0


class Solution:

	def isRepeat(self, s):
		n = len(s)
		for i in range(1, n):
			if n % i == 0:
				substring = s[:i]
				new_str = substring
				while len(new_str) < n:
					new_str += substring
				if new_str == s:
					return 1
		return 0


class Solution:

	def isRepeat(self, s):
		l = len(s)
		for i in range(l // 2, 0, -1):
			if l % i == 0:
				r = l // i
				st = s[0:i]
				m = ''
				while r != 0:
					m = m + st
					r = r - 1
				if m == s:
					return 1
		return 0


class Solution:

	def isRepeat(self, str1):
		n = len(str1)
		flag = 0
		for i in range(0, len(str1) // 2):
			sub = str1[0:i + 1]
			l = len(sub)
			exp = n // l
			if sub * exp == str1:
				return 1
		return 0


from collections import Counter
import math

class Solution:

	def isRepeat(self, s):
		len_s = len(s)
		if len_s <= 1:
			return 0
		i = len_s // 2
		j = 0
		while j < i:
			if s[:j + 1] * (len_s // (j + 1)) == s:
				return 1
			j += 1
		return 0


class Solution:

	def isRepeat(self, s):
		if len(s) <= 1:
			return 0
		p = ''
		c = 0
		l = len(s)
		for i in s:
			p = p + i
			c = c + 1
			k = l // c
			if k > 1 and s == p * k:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		n = len(s)
		for i in range(1, n):
			if n % i == 0 and s[:i] * (n // i) == s:
				return 1
		return 0


class Solution:

	def calc(self, s):
		n = len(s)
		lps = [0] * n
		for i in range(1, n):
			j = lps[i - 1]
			while j > 0 and s[j] != s[i]:
				j = lps[j - 1]
			if s[i] == s[j]:
				j += 1
			lps[i] = j
		return lps

	def isRepeat(self, s):
		lps = self.calc(s)
		n = len(s)
		return 1 if lps[n - 1] != 0 and n % (n - lps[n - 1]) == 0 else 0


class Solution:

	def isRepeat(self, s):
		for l in range(len(s) // 2, 0, -1):
			if len(s) % l == 0:
				i = 0
				while i + l < len(s) and s[i] == s[i + l]:
					i += 1
				if l + i == len(s):
					return 1
		return 0


class Solution:

	def isRepeat(self, s):
		n = len(s)
		a = []
		for i in range(1, n // 2 + 1):
			if n % i == 0:
				a.append(i)
		i = len(a) - 1
		while i >= 0:
			j = 0
			while (j + 2) * a[i] <= len(s) and s[j * a[i]:(j + 1) * a[i]] == s[(j + 1) * a[i]:(j + 2) * a[i]]:
				j += 1
			if (j + 2) * a[i] > len(s):
				return 1
			i -= 1
		return 0


class Solution:

	def zalgo(self, s):
		res = [0 for i in s]
		(l, r, k) = (0, 0, 0)
		for i in range(1, len(s)):
			if i > r:
				(l, r) = (i, i)
				while r < len(s) and s[r] == s[r - l]:
					r += 1
				res[i] = r - l
				r -= 1
			elif i + res[i - l] <= r:
				res[i] = res[i - l]
			else:
				l = i
				while r < len(s) and s[r] == s[r - l]:
					r += 1
				res[i] = r - l
				r -= 1
		return res

	def isRepeat(self, s):
		z = self.zalgo(s)
		l = max(z)
		if l == 0:
			return 0
		if z[-l] == l:
			return int(len(s) % (len(s) - l) == 0)
		return 0


class Solution:

	def isRepeat(self, s):
		n = len(s)
		for i in range(1, n // 2 + 1):
			if n % i:
				continue
			flag = True
			for j in range(i, n, i):
				if s[:i] != s[j:j + i]:
					flag = False
					break
			if flag:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		p = ''
		c = 0
		n = len(s)
		for i in s:
			p += i
			c += 1
			ss = n // c
			if ss > 1 and s == p * ss:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		sub_s = ''
		for i in range(len(s) - 1):
			sub_s += s[i]
			construc_s = sub_s * (len(s) // len(sub_s))
			if construc_s == s:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		r = len(s) // 2
		if s[:r] == s[r:]:
			return 1
		else:
			if r != 1:
				r -= 1
			while r > 0:
				if (len(s) - r) % r != 0:
					r -= 1
				else:
					t = s[:r]
					i = r
					while i < len(s):
						if s[i:i + len(t)] != t:
							r -= 1
							break
						i += len(t)
					if i == len(s):
						return 1
			return 0


class Solution:

	def isRepeat(self, s):
		n = len(s)
		lps = [0] * n
		i = 0
		j = 1
		while j < n:
			if s[i] == s[j]:
				lps[j] = i + 1
				i += 1
				j += 1
			elif i == 0:
				lps[j] = 0
				j += 1
			else:
				i = lps[i - 1]
		if lps[n - 1] == 0:
			return 0
		if n % (n - lps[n - 1]) == 0:
			return 1
		else:
			return 0


class Solution:

	def isRepeat(self, s):
		if not s:
			return
		len_s = len(s)
		if len_s <= 1:
			return 0
		i = len_s // 2
		j = 0
		while j < i:
			if s[:j + 1] * (len_s // (j + 1)) == s:
				return 1
			j += 1
		return 0


class Solution:

	def isRepeat(self, s):
		for i in range(1, len(s) // 2 + 1):
			if len(s) % i == 0:
				substring = s[:i]
			if substring * (len(s) // len(substring)) == s:
				return 1
		return 0


class Solution:

	def isRepeat(self, pat):
		m = len(pat)
		lps = [0] * m
		length = 0
		i = 1
		while i < m:
			if pat[i] == pat[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length == 0:
				lps[i] = 0
				i += 1
			else:
				length = lps[length - 1]
		if lps[-1] == 0:
			return 0
		lengthPat = m - lps[-1]
		if m % lengthPat == 0:
			return 1
		return 0


class Solution:

	def isRepeat(self, s):
		string = len(s)
		if string <= 1:
			return 0
		p = string // 2
		q = 0
		while q < p:
			if s[:q + 1] * (string // (q + 1)) == s:
				return 1
			q += 1
		return 0


class Solution:

	def isRepeat(self, s):
		S = s + s
		if s in S[1:-1]:
			return 1
		return 0


class Solution:

	def computeLPSArray(self, str, M, lps):
		lps[0] = 0
		i = 1
		length = 0
		while i < M:
			if str[i] == str[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1

	def isRepeat(self, string):
		n = len(string)
		lps = [0] * n
		Solution.computeLPSArray(self, string, n, lps)
		length = lps[n - 1]
		if length > 0 and n % (n - length) == 0:
			return 1
		else:
			return 0


class Solution:

	def isRepeat(self, A):
		n = len(A)
		lps = [0] * n
		for i in range(1, n):
			x = lps[i - 1]
			while A[x] != A[i]:
				if x == 0:
					x = -1
					break
				x = lps[x - 1]
			lps[i] = x + 1
		if lps[-1] > 0 and n % (n - lps[-1]) == 0:
			return 1
		else:
			return 0


class Solution:

	def isRepeat(self, s):
		temp = ''
		cnt = 0
		n = len(s)
		for i in s:
			temp += i
			cnt += 1
			l = n // cnt
			if l > 1 and temp * l == s:
				return 1
		return 0


def is_possible(string, pat):
	if len(string) == 0:
		return 1
	if len(string) < len(pat):
		return 0
	pat_len = len(pat)
	if string[:pat_len] != pat:
		return 0
	return is_possible(string[pat_len:], pat)

class Solution:

	def isRepeat(self, s):
		s_len = len(s)
		for i in range(1, s_len):
			if s_len % i != 0:
				continue
			if is_possible(s[i:], s[:i]):
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		l = len(s)
		for i in range(1, l // 2 + 1):
			if l % i == 0:
				j = l // i
				x = s[:i] * j
				if x == s:
					return 1
		return 0


class Solution:

	def isRepeat(self, s):

		def _r(s):
			lps = [0]
			le = 0
			i = 1
			m = len(s)
			while i < m:
				if s[i] == s[le]:
					le += 1
					i += 1
					lps.append(le)
				elif le == 0:
					i += 1
					lps.append(0)
				else:
					le = lps[le - 1]
			if lps:
				return (s[0:lps[len(lps) - 1]], lps.pop())
			else:
				return ('', 0)
		(temp, div) = _r(s)
		n = len(s)
		if div == 0:
			return 0
		elif n % (n - div) != 0:
			return 0
		else:
			return 1


class Solution:

	def isRepeat(self, S):
		if len(S) == 1:
			return 0
		else:
			ans = 0
			for i in range(1, len(S) // 2 + 1):
				p = s[:i]
				if len(S) % len(p) == 0 and S.count(p) == len(S) // len(p):
					return 1
			return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def isRepeat(self, s):
		len_s = len(s)
		if len_s <= 1:
			return 0
		i = len_s // 2
		j = 0
		while j < i:
			if s[:j + 1] * (len_s // (j + 1)) == s:
				return 1
			j += 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def isRepeat(self, s):
		p = ''
		c = 0
		n = len(s)
		for i in s:
			p += i
			c += 1
			l = n // c
			if l > 1 and s == p * l:
				return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def isRepeat(self, s):
		lp = [0] * len(s)
		lp[0] = 0
		leni = 0
		i = 1
		m = len(s)
		while i < m:
			if s[leni] == s[i]:
				lp[i] = leni + 1
				i += 1
				leni += 1
			elif leni != 0:
				leni = lp[leni - 1]
			else:
				lp[i] = 0
				i += 1
		length = lp[len(s) - 1]
		if length > 0 and len(s) % (len(s) - length) == 0:
			return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def isRepeat(self, s):
		r = len(s) // 2
		if s[:r] == s[r:]:
			return 1
		else:
			if r != 1:
				r -= 1
			while r > 0:
				if (len(s) - r) % r != 0:
					r -= 1
				else:
					t = s[:r]
					i = r
					while i < len(s):
						if s[i:i + len(t)] != t:
							r -= 1
							break
						i += len(t)
					if i == len(s):
						return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def isRepeat(self, s):
		mp = {}
		n = len(s)
		temp = ''
		for i in range(n // 2):
			temp += s[i]
			if len(s) % len(temp) == 0:
				if temp * (len(s) // len(temp)) == s:
					return 1
		return 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def constructLPS(self, s):
		n = len(s)
		lps = [0] * n
		l = 0
		i = 1
		while i < n:
			if s[i] == s[l]:
				l += 1
				lps[i] = l
				i += 1
			elif l != 0:
				l = lps[l - 1]
			else:
				lps[i] = 0
				i = i + 1
		return lps

	def isRepeat(self, s):
		lps = self.constructLPS(s)
		last = lps[-1]
		res = last > 0 and len(s) % (len(s) - last) == 0
		return 1 if res else 0
if __name__ == '__main__':
	T = int(input())
	for i in range(T):
		s = input()
		ob = Solution()
		answer = ob.isRepeat(s)
		print(answer)


class Solution:

	def isRepeat(self, s):
		if len(s) <= 1:
			return 0
		else:
			sub_s = ''
			len_s = len(s)
			for i in range(0, int(len_s / 2)):
				sub_s += s[i]
				check_s = sub_s * int(len_s / len(sub_s))
				if check_s == s:
					return 1
			return 0


class Solution:

	def isRepeat(self, s):
		k = 1
		i = 0
		if len(s) == 2:
			if s[i] == s[i + 1]:
				return 1
		while k < len(s):
			if s[i] == s[k]:
				i += 1
				k += 1
				m = k
				while k < len(s):
					if s[i] == s[k]:
						if k == len(s) - 1:
							if s[0:k - i] == s[i + 1:k + 1]:
								return 1
							else:
								return 0
						i += 1
						k += 1
					else:
						i = 0
						k = m
						break
			else:
				k += 1
		return 0


class Solution:

	def isRepeat(self, s):
		return int(s in (2 * s)[1:-1])


class Solution:

	def isRepeat(self, s):
		factors = []
		string_len = len(s)
		for i in range(1, len(s)):
			if string_len % i == 0:
				factors.append(i)
		for i in factors:
			if s[:i] * int(len(s) / i) == s:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		if len(s) <= 1:
			return 0
		else:

			def rep(sub, s):
				re = ''
				n = len(s) // len(sub)
				re = sub * n
				if re == s:
					return True
				else:
					return False
			c = 0
			for i in range(len(s) // 2):
				sub = s[0:i + 1]
				ans = rep(sub, s)
				if ans:
					c = 1
					break
			if c == 1:
				return 1
			else:
				return 0


class Solution:

	def isRepeat(self, s):

		def check(s, s1):
			k = len(s1)
			for i in range(0, len(s), k):
				s2 = s[i:i + k]
				if s2 != s1:
					return False
			return True
		sum = 0
		for i in s:
			sum = sum + ord(i)
		s1 = ''
		checksum = 0
		for i in s:
			checksum = checksum + ord(i)
			s1 = s1 + i
			if sum % checksum == 0 and len(s) % len(s1) == 0 and (s != s1) and check(s, s1):
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		temp = ''
		ans = ''
		for i in range(len(s) - 1):
			temp += s[i]
			if len(s) % len(temp) == 0 and temp * (len(s) // len(temp)) == s:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		n = len(s)
		k = 0
		j = 1
		while k + j < n:
			if s[k] == s[k + j]:
				k += 1
			elif s[k] != s[k + j]:
				j += 1
				k = 0
		if k > 0 and n % (n - k) == 0:
			return 1
		return 0


class Solution:

	def p(self, s):
		pi = [0 for i in range(len(s))]
		q = 0
		for i in range(1, len(s)):
			while q > 0 and s[q] != s[i]:
				q = pi[q - 1]
			if s[i] == s[q]:
				q += 1
			pi[i] = q
		return pi

	def isRepeat(self, s):
		n = len(s)
		pi = self.p(s)
		x = n - pi[n - 1]
		if x != n and n % x == 0:
			return 1
		return 0


class Solution:

	def isRepeat(self, s):
		if len(s) <= 1:
			return 0
		for i in range(len(s) // 2):
			sub = s[:i + 1]
			currLen = int(len(s) / len(sub))
			if sub * currLen == s:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		M = len(s)
		lps = [0] * M
		length = 0
		lps[0] = 0
		i = 1
		while i < M:
			if s[i] == s[length]:
				length += 1
				lps[i] = length
				i += 1
			elif length != 0:
				length = lps[length - 1]
			else:
				lps[i] = 0
				i += 1
		length = lps[M - 1]
		return 1 if length > 0 and M % (M - length) == 0 else 0


class Solution:

	def isRepeat(self, s):
		c = 0
		for i in s:
			n = len(s)
			a = s[0:n // 2 - c]
			if len(a) > 0:
				x = n // len(a)
				c += 1
				if a * x == s:
					return 1
				else:
					ans = False
			else:
				return 0
		if ans == False:
			return 0


class Solution:

	def isRepeat(self, s):
		p = ''
		c = 0
		d = 0
		for j in s:
			p += j
			c += 1
			d = len(s) // c
			if d > 1 and s == p * d:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		l = len(s)
		factors = []
		k = 1

		def check_rep(n):
			l = int(len(s) / n)
			s2 = ''
			s3 = ''
			for i in range(0, n):
				s2 += s[i]
			for t in range(0, l):
				s3 += s2
				t += 1
			if s3 == s:
				return 1
			else:
				return 0
		for k in range(1, l):
			if l % k == 0:
				factors.append(k)
		for factor in factors:
			if check_rep(factor):
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		for i in range(1, len(s)):
			mul = int(len(s) / i)
			if s[0:i] * mul == s:
				return 1
		return 0


class Solution:

	def isRepeat(self, s):
		for i in range(len(s) // 2):
			ch = s[0:i + 1]
			left = len(s) - (i + 1)
			if left % len(ch) == 0:
				repeat = ch * (left // len(ch) + 1)
				if repeat == s:
					return 1
		return 0


class Solution:

	def isRepeat(self, s):
		cur = s[0]
		k = len(s) // 2
		for i in range(1, k + 1):
			if cur * (len(s) // i) == s:
				return 1
			else:
				cur += s[i]
		return 0