AtCoder Regular Contest 060 - Best Representation

Let x be a string of length at least 1.
We will call x a good string, if for any string y and any integer k (k \geq 2), the string obtained by concatenating k copies of y is different from x.
For example, a, bbc and cdcdc are good strings, while aa, bbbb and cdcdcd are not.
Let w be a string of length at least 1.
For a sequence F=(\,f_1,\,f_2,\,...,\,f_m) consisting of m elements,
we will call F a good representation of w, if the following conditions are both satisfied:
 - For any i \, (1 \leq i \leq m), f_i is a good string.
 - The string obtained by concatenating f_1,\,f_2,\,...,\,f_m in this order, is w.
For example, when w=aabb, there are five good representations of w:
 - (aabb)
 - (a,abb)
 - (aab,b)
 - (a,ab,b)
 - (a,a,b,b)
Among the good representations of w, the ones with the smallest number of elements are called the best representations of w.
For example, there are only one best representation of w=aabb: (aabb).
You are given a string w. Find the following:
 - the number of elements of a best representation of w
 - the number of the best representations of w, modulo 1000000007 \, (=10^9+7)
(It is guaranteed that a good representation of w always exists.)

-----Constraints-----
 - 1 \leq |w| \leq 500000 \, (=5 \times 10^5)
 - w consists of lowercase letters (a-z).

-----Partial Score-----
 - 400 points will be awarded for passing the test set satisfying 1 \leq |w| \leq 4000.

-----Input-----
The input is given from Standard Input in the following format:
w

-----Output-----
Print 2 lines.
 - In the first line, print the number of elements of a best representation of w.
 - In the second line, print the number of the best representations of w, modulo 1000000007.

-----Sample Input-----
aab

-----Sample Output-----
1
1

Source: atcoder | Difficulty: VERY_HARD


Solutions:
w = list(input())
n = len(w)
t = -1

def Z(s):
	m = len(s)
	z = [0] * m
	c = 0
	f = [1] * m
	for i in range(1, m):
		if i + z[i - c] < c + z[c]:
			z[i] = z[i - c]
		else:
			j = max(0, c + z[c] - i)
			while i + j < n and s[j] == s[i + j]:
				j = j + 1
			z[i] = j
			c = i
	for p in range(1, m):
		for k in range(2, z[p] // p + 2):
			f[k * p - 1] = 0
	return f
for j in range(1, n // 2 + 1):
	if n % j == 0 and w[:n - j] == w[j:]:
		t = j
		break
if t == -1:
	print('1\n1')
elif t == 1:
	print(n)
	print(1)
else:
	zl = Z(w)
	w.reverse()
	zr = Z(w)
	cnt = 0
	for i in range(0, n - 1):
		if zl[i] and zr[n - 2 - i]:
			cnt = cnt + 1
	print(2)
	print(cnt)


def Z_algorithm(S):
	l = len(S)
	A = [0] * l
	A[0] = l
	i = 1
	j = 0
	while i < l:
		while i + j < l and S[j] == S[i + j]:
			j += 1
		if not j:
			i += 1
			continue
		A[i] = j
		k = 1
		while l - i > k < j - A[k]:
			A[i + k] = A[k]
			k += 1
		i += k
		j -= k
	return A

def jugde(W):
	Z = Z_algorithm(W)
	l = len(W)
	B = [True] * l
	for p in range(1, l):
		if not B[p - 1]:
			continue
		k = 2
		while (k - 1) * p <= Z[p]:
			B[k * p - 1] = False
			k += 1
	return B

def solve(W):
	n = len(W)
	if len(set(W)) == 1:
		print(n)
		print(1)
		return
	G = jugde(W)
	W.reverse()
	G_rev = jugde(W)
	if G[-1]:
		print(1)
		print(1)
		return
	print(2)
	cnt = 0
	for i in range(n - 1):
		cnt += G[i] and G_rev[-(i + 2)]
	print(cnt)
	return
solve(list(input()))


import sys
readline = sys.stdin.readline

class Rollinhash:

	def __init__(self, S):
		N = len(S)
		self.mod = 10 ** 9 + 9
		self.base = 2009
		self.has = [0] * (N + 1)
		self.power = [1] * (N + 1)
		for i in range(N):
			s = S[i]
			self.has[i + 1] = (self.has[i] * self.base + s) % self.mod
			self.power[i + 1] = self.power[i] * self.base % self.mod

	def rh(self, i, j):
		return (self.has[j] - self.has[i] * self.power[j - i]) % self.mod
MOD = 10 ** 9 + 7
S = list(map(ord, readline().strip()))
N = len(S)
if len(set(S)) == 1:
	print(N)
	print(1)
else:
	Rs = Rollinhash(S)
	tabler = [True] * (N + 1)
	for d in range(1, 1 + N // 2):
		r = Rs.rh(0, d)
		for i in range(1, N // d):
			if r != Rs.rh(i * d, (i + 1) * d):
				break
			tabler[(i + 1) * d] = False
	tablel = [True] * (N + 1)
	for d in range(1, 1 + N // 2):
		r = Rs.rh(N - d, N)
		for i in range(1, N // d):
			if r != Rs.rh(N - (i + 1) * d, N - i * d):
				break
			tablel[N - (i + 1) * d] = False
	if tabler[N]:
		print(1)
		print(1)
	else:
		print(2)
		ans = 0
		for i in range(N + 1):
			if tabler[i] and tablel[i]:
				ans += 1
		assert ans > 0, ''
		print(ans)


from collections import Counter
(*W,) = map(ord, input())
N = len(W)
C = Counter(W)
if len(C) == 1:
	print(N)
	print(1)
	return

def z_algo(S):
	A = [0] * N
	i = 1
	j = 0
	A[0] = l = len(S)
	while i < l:
		while i + j < l and S[j] == S[i + j]:
			j += 1
		A[i] = j
		if not j:
			i += 1
			continue
		k = 1
		while l - i > k < j - A[k]:
			A[i + k] = A[k]
			k += 1
		i += k
		j -= k
	return A

def calc(W):
	Z = z_algo(W)
	G = [0] * N
	for i in range(N):
		G[i] = 1
	for p in range(1, N):
		if not G[p - 1]:
			continue
		for k in range(2, Z[p] // p + 2):
			G[k * p - 1] = 0
	return G
G0 = calc(W)
W.reverse()
G1 = calc(W)
if G0[N - 1]:
	print(1)
	print(1)
	return
print(2)
print(sum((p and q for (p, q) in zip(G0[:-1], reversed(G1[:-1])))))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
W = read().rstrip()
N = len(W)

def Z_algorithm(S):
	N = len(S)
	arr = [0] * N
	arr[0] = N
	(i, j) = (1, 0)
	while i < N:
		while i + j < N and S[j] == S[i + j]:
			j += 1
		arr[i] = j
		if not j:
			i += 1
			continue
		k = 1
		while i + k < N and k + arr[k] < j:
			arr[i + k] = arr[k]
			k += 1
		i += k
		j -= k
	return arr

def is_periodic_left(W):
	Z = Z_algorithm(W)
	is_periodic = [False] * N
	for p in range(1, N // 2 + 1):
		if is_periodic[p - 1]:
			continue
		for i in range(p, N, p):
			if Z[i] >= p:
				is_periodic[p + i - 1] = True
			else:
				break
	return is_periodic
L = is_periodic_left(W)
R = is_periodic_left(W[::-1])[::-1]
if not L[-1]:
	answer = (1, 1)
elif len(set(W)) == 1:
	answer = (N, 1)
else:
	x = sum((not (x or y) for (x, y) in zip(L, R[1:])))
	answer = (2, x)
print('\n'.join(map(str, answer)))


import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
W = list(map(int, read().rstrip()))
N = len(W)

def Z_Algorithm(S):
	N = len(S)
	arr = [0] * N
	arr[0] = N
	(i, j) = (1, 0)
	while i < N:
		while i + j < N and S[j] == S[i + j]:
			j += 1
		arr[i] = j
		if not j:
			i += 1
			continue
		k = 1
		while i + k < N and k + arr[k] < j:
			arr[i + k] = arr[k]
			k += 1
		i += k
		j -= k
	return arr

def find_good_substr(W):
	Z = Z_Algorithm(W)
	is_good = [True] * (N + 1)
	for n in range(1, N // 2 + 1):
		if not is_good[n]:
			continue
		for i in range(n + n, Z[n] + n + 1, n):
			is_good[i] = False
	return is_good

def solve():
	G1 = find_good_substr(W)
	G2 = find_good_substr(W[::-1])[::-1]
	if G1[-1]:
		return (1, 1)
	if len(set(W)) == 1:
		return (N, 1)
	x = sum((x and y for (x, y) in zip(G1[1:-1], G2[1:-1])))
	return (2, x)
(x, y) = solve()
print(x)
print(y)