You have a string s = s_1s_2...s_{|}s|, where |s| is the length of string s, and s_{i} its i-th character. 

Let's introduce several definitions:  A substring s[i..j] (1 ≤ i ≤ j ≤ |s|) of string s is string s_{i}s_{i} + 1...s_{j}.  The prefix of string s of length l (1 ≤ l ≤ |s|) is string s[1..l].  The suffix of string s of length l (1 ≤ l ≤ |s|) is string s[|s| - l + 1..|s|]. 

Your task is, for any prefix of string s which matches a suffix of string s, print the number of times it occurs in string s as a substring.


-----Input-----

The single line contains a sequence of characters s_1s_2...s_{|}s| (1 ≤ |s| ≤ 10^5) — string s. The string only consists of uppercase English letters.


-----Output-----

In the first line, print integer k (0 ≤ k ≤ |s|) — the number of prefixes that match a suffix of string s. Next print k lines, in each line print two integers l_{i} c_{i}. Numbers l_{i} c_{i} mean that the prefix of the length l_{i} matches the suffix of length l_{i} and occurs in string s as a substring c_{i} times. Print pairs l_{i} c_{i} in the order of increasing l_{i}.


-----Examples-----
Input
ABACABA

Output
3
1 4
3 2
7 1

Input
AAA

Output
3
1 3
2 2
3 1

Source: codeforces | Difficulty: HARD
Tags: String algorithms

Dynamic programming

Amortized analysis


Solutions:
def Count(s, t):
	res = 0
	for i in range(len(s) - len(t) + 1):
		if s[i:i + len(t)] == t:
			res += 1
	return res
s = input()
n = len(s)
p = [0] * n
z = [0] * n
ans = [0] * n
for i in range(1, n):
	p[i] = p[i - 1]
	while p[i] > 0 and s[i] != s[p[i]]:
		p[i] = p[p[i] - 1]
	if s[i] == s[p[i]]:
		p[i] += 1
l = r = 0
for i in range(1, n):
	if i <= r:
		z[i] = min(z[i - l], r - i + 1)
	while i + z[i] < n and s[i + z[i]] == s[z[i]]:
		z[i] += 1
	if i + z[i] - 1 > r:
		(l, r) = (i, i + z[i] - 1)
for i in range(n):
	if z[i] > 0:
		ans[z[i] - 1] += 1
for i in range(n - 2, -1, -1):
	ans[i] += ans[i + 1]
output = []
for i in range(n):
	if z[n - i - 1] == i + 1:
		output.append((i, ans[i]))
print(len(output) + 1)
for i in range(len(output)):
	print(output[i][0] + 1, output[i][1] + 1)
print(n, 1)


import sys
import random
import bisect
from collections import deque
from queue import PriorityQueue
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7

def zfunc(s):
	n = len(s)
	z = [0 for i in range(n)]
	l = 0
	r = 0
	for i in range(1, n):
		if i <= r:
			z[i] = min(r - i + 1, z[i - l])
		while i + z[i] < n and s[z[i]] == s[i + z[i]]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z
s = ip()
n = len(s)
mn = zfunc(s)
ans = []
d = {}
for i in range(1, n):
	if i + mn[i] == n:
		m1 = 2
		ans.append([mn[i], m1])
x2 = mn.copy()
x2.sort()
ans.append([n, 1])
ans.sort()
for i in range(len(ans) - 1):
	m2 = bisect.bisect_left(x2, ans[i][0])
	ans[i][1] += n - m2 - 1
print(len(ans))
for i in ans:
	print(*i)


def computeLPSArray(pat, M, lps):
	len = 0
	lps[0]
	i = 1
	while i < M:
		if pat[i] == pat[len]:
			len += 1
			lps[i] = len
			i += 1
		elif len != 0:
			len = lps[len - 1]
		else:
			lps[i] = 0
			i += 1
	return lps

def count_subs_occ(s, m, l):
	occ = [0] * (m + 1)
	for i in range(m):
		occ[l[i]] += 1
	for i in range(m - 1, 0, -1):
		occ[l[i - 1]] += occ[i]
	for i in range(m + 1):
		occ[i] += 1
	return occ
s = input()
m = len(s)
l = [0] * m
x = computeLPSArray(s, m, l)
x = [0] + x
y = count_subs_occ(s, m, l)
a = x[-1]
if a == 0:
	print(1)
	print(m, 1)
elif a == 1:
	print(2)
	print(1, y[a])
	print(m, 1)
else:
	u = x[-1]
	v = x[u]
	ans = [[u, y[u]]]
	while 1:
		if v == 0:
			break
		u = v
		v = x[u]
		temp = [u, y[u]]
		ans.append(temp)
	ans.sort()
	print(len(ans) + 1)
	for i in range(len(ans)):
		print(ans[i][0], ans[i][1])
	print(m, 1)


from sys import stdin
from collections import deque
from math import sqrt, floor, ceil, log, log2, log10, pi, gcd, sin, cos, asin

def ii():
	return int(stdin.readline())

def fi():
	return float(stdin.readline())

def mi():
	return map(int, stdin.readline().split())

def fmi():
	return map(float, stdin.readline().split())

def li():
	return list(mi())

def lsi():
	x = list(stdin.readline())
	x.pop()
	return x

def si():
	return stdin.readline()
res = ['YES', 'NO']

def create_z(s):
	z = [0] * len(s)
	x = y = 0
	for i in range(1, len(s)):
		z[i] = max(0, min(z[i - x], y - i + 1))
		while i + z[i] < len(s) and s[z[i]] == s[i + z[i]]:
			x = i
			y = i + z[i]
			z[i] += 1
	return z
a = create_z(lsi())
x = [[len(a), 1]]
s = set()
for i in range(len(a)):
	if i + a[i] == len(a):
		s.add(a[i])
a.sort(reverse=True)
c = 2
for i in range(len(a) - 1):
	if a[i] == 0:
		break
	if a[i] not in s:
		c += 1
		continue
	if a[i] != a[i + 1]:
		x.append([a[i], c])
	c += 1
print(len(x))
for i in reversed(x):
	print(*i)


s = ' ' + input()
n = len(s)
(r, c) = ([-1] * n, [1] * n)
for i in range(1, n):
	r[i] = r[i - 1] + 1
	while r[i] and s[r[i]] != s[i]:
		r[i] = r[r[i] - 1] + 1
(d, n) = ([], n - 1)
for i in range(n, 1, -1):
	c[r[i]] += c[i]
while n > 0:
	d.append(str(n) + ' ' + str(c[n]))
	n = r[n]
print(len(d))
d.reverse()
print('\n'.join(d))


s = input()
n = len(s)
if n == 1:
	print(1)
	print(1, 1)
	quit()
priya = [-1] * n
q = -1
for i in range(1, n):
	while q >= 0 and s[i] != s[q + 1]:
		q = priya[q]
	if s[i] == s[q + 1]:
		q += 1
		priya[i] = q
cnt = [1] * n
for i in range(n - 1, -1, -1):
	if priya[i] >= 0:
		cnt[priya[i]] += cnt[i]
Ans = [(n, 1)]
q = priya[n - 1]
while q >= 0:
	Ans.append((q + 1, cnt[q]))
	q = priya[q]
Ans.sort()
print(len(Ans))
for i in Ans:
	print(*i)


s = input()
n = len(s)
m = [0] * (n + 1)
z = [0] * (n + 1)
l = 0
r = 0
li = [n]
for i in range(1, n):
	if i <= r:
		z[i] = min(r - i + 1, z[i - l])
	while i + z[i] < n and s[z[i]] == s[i + z[i]]:
		z[i] += 1
	if i + z[i] - 1 > r:
		l = i
		r = i + z[i] - 1
	m[z[i]] += 1
	if i + z[i] == n:
		li.append(z[i])
for i in range(n - 1, 0, -1):
	m[i] += m[i + 1]
li.reverse()
print(len(li))
for i in range(0, len(li)):
	print(li[i], m[li[i]] + 1)


import sys
input = sys.stdin.readline
s = input().rstrip()
n = len(s)
i = 1
j = 0
a = [0] * n
a[0] = n
while i < n:
	while i + j < n and s[j] == s[i + j]:
		j += 1
	a[i] = j
	if j == 0:
		i += 1
		continue
	k = 1
	while i + k < n and k + a[k] < j:
		a[i + k] = a[k]
		k += 1
	i += k
	j -= k
ans = [0] * (n + 1)
for aa in a:
	ans[aa] += 1
for i in range(n)[::-1]:
	ans[i] += ans[i + 1]
ans2 = []
for i in range(1, n + 1):
	if a[n - i] == i:
		ans2.append([i, ans[i]])
print(len(ans2))
for x in ans2:
	print(*x)


dep = dict()

def kmp(st):
	tam = len(st)
	pi = [0] * tam
	for i in range(1, tam):
		j = pi[i - 1]
		while j > 0 and st[j] != st[i]:
			j = pi[j - 1]
		if st[j] == st[i]:
			pi[i] = j + 1
		dep[pi[i]] = pi[pi[i] - 1]
	return pi
s = input()
arr = kmp(s)
points = [0] * len(s)
toimp = list()
actpi = arr[-1]
while actpi != 0:
	toimp.append(actpi)
	actpi = arr[actpi - 1]
toimp.sort()
for i in range(len(arr)):
	points[arr[i]] += 1
for i in range(len(s) - 1, 0, -1):
	if i in dep:
		points[dep[i]] += points[i]
print(len(toimp) + 1)
for i in toimp:
	print(str(i) + ' ' + str(points[i] + 1))
print(str(len(s)) + ' 1')


def zfunc(s):
	n = len(s)
	z = [0] * n
	left = right = 0
	for i in range(1, n):
		if i <= right:
			z[i] = min(z[i - left], right - i + 1)
		while i + z[i] < n and s[z[i]] == s[i + z[i]]:
			z[i] += 1
		if i + z[i] - 1 > right:
			(left, right) = (i, i + z[i] - 1)
	return z
s = input()
ans = set()
z = zfunc(s)
z[0] = len(s)
res = [0] * (len(s) + 1)
for i in z:
	res[i] += 1
from itertools import accumulate
res = [*accumulate(res[::-1])][::-1]
for (i, j) in enumerate(z[::-1]):
	if j > i:
		ans.add((j, res[j]))
print(len(ans))
for i in sorted([*ans]):
	print(*i)


import sys
import bisect
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
gp = []
cost = []
dp = []
mx = []

def dfs(root, par):
	global gp, cost, dp
	dp[root] = cost[root]
	for i in gp[root]:
		if i == par:
			continue
		dfs(i, root)
		dp[root] = max(dp[root], dp[i])

def z_algo(ar):
	n = len(ar)
	ans = [0] * n
	(l, r) = (0, 0)
	ans[0] = n
	for i in range(1, n):
		if i <= r:
			ans[i] = min(r - i + 1, ans[i - l])
		while i + ans[i] < n and ar[ans[i]] == ar[i + ans[i]]:
			ans[i] += 1
		if i + ans[i] - 1 > r:
			l = i
			r = i + ans[i] - 1
	return ans

def hnbhai():
	s = sa()
	n = len(s)
	z = z_algo(s)
	count = [0] * (n + 1)
	mark = [0] * (n + 1)
	tot = 0
	for i in range(n - 1, -1, -1):
		if z[i] + i == n:
			mark[z[i]] = 1
			tot += 1
	for i in range(n):
		count[z[i]] += 1
	for i in range(n - 1, -1, -1):
		count[i] += count[i + 1]
	print(tot)
	for i in range(1, n + 1):
		if mark[i]:
			print(i, count[i])
for _ in range(1):
	hnbhai()


def calculate_z_array(s):
	n = len(s)
	z = [0] * n
	z[0] = n
	l = 0
	r = 0
	for i in range(1, n):
		if i >= l and i <= r:
			z[i] = min(z[i - l], r - i + 1)
		while i + z[i] < n and s[z[i]] == s[z[i] + i]:
			z[i] += 1
		if i + z[i] - 1 < n and i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z
s = input()
n = len(s)
z = calculate_z_array(s)
no_of_prefix_suffix = 0
is_prefix_sufix = [False] * (n + 1)
for i in range(n):
	if i + z[i] == n:
		no_of_prefix_suffix += 1
		is_prefix_sufix[z[i]] = True
cnt = [0] * (n + 1)
for i in range(n):
	cnt[z[i]] += 1
for i in range(n - 1, -1, -1):
	cnt[i] += cnt[i + 1]
print(no_of_prefix_suffix)
for i in range(1, n + 1):
	if is_prefix_sufix[i] == True:
		print(i, ' ', cnt[i])


s = input()
n = len(s)
if n == 1:
	print('1\n1 1\n')
	exit()
p = [-1] * n
q = -1
for i in range(1, n):
	while q >= 0 and s[i] != s[q + 1]:
		q = p[q]
	if s[i] == s[q + 1]:
		q += 1
		p[i] = q
c = [1] * n
for i in range(n - 1, -1, -1):
	if p[i] >= 0:
		c[p[i]] += c[i]
ans = [(n, 1)]
q = p[n - 1]
while q >= 0:
	ans.append((q + 1, c[q]))
	q = p[q]
print(len(ans))
print('\n'.join([' '.join(map(str, x)) for x in reversed(ans)]))


s = input()
n = len(s)
z = [0] * n
l = 0
r = 0
for i in range(1, n):
	if s[i] == s[0]:
		if i < r:
			j = i + min(z[i - l], r - i)
			while j < n and s[j] == s[j - i]:
				j += 1
			z[i] = j - i
			if j > r:
				l = i
				r = j
		else:
			l = i
			r = i + 1
			while r < n and s[r] == s[r - l]:
				r += 1
			z[i] = r - l
	else:
		z[i] = 0
a = []
c = [0] * n
for i in range(1, n):
	if i + z[i] == n:
		a.append(z[i])
	c[z[i]] += 1
for i in reversed(range(n - 1)):
	c[i] += c[i + 1]
print(len(a) + 1)
for x in sorted(a):
	print(x, c[x] + 1)
print(n, 1)


def prefixFunction(s):
	j = 0
	p = [0 for x in s]
	for i in range(1, len(s)):
		while j > 0 and s[j] != s[i]:
			j = p[j - 1]
		if s[j] == s[i]:
			j += 1
		p[i] = j
	return p
s = input()
p = prefixFunction(s)
n = len(s)
freq = [0 for i in range(n)]
for i in range(n):
	freq[p[i]] += 1
for i in range(n - 1, 0, -1):
	freq[p[i - 1]] += freq[i]
pos = n - 1
ans = [[n, 1]]
while pos > 0:
	if p[pos] > 1:
		ans.append([p[pos], freq[p[pos]] + 1])
	pos = p[pos] - 1
if len(s) > 1:
	f = s.count(s[0])
	if s[0] == s[len(s) - 1]:
		ans.append([1, f])
print(len(ans))
for i in sorted(ans):
	print(i[0], i[1])


def getLPS(s2, l):
	lps = [0] * l
	i = 1
	j = 0
	while i < l:
		if s2[i] == s2[j]:
			lps[i] = j + 1
			j += 1
			i += 1
		elif j != 0:
			j = lps[j - 1]
		else:
			lps[i] = 0
			i += 1
	return lps
s = input()
n = len(s)
p = getLPS(s, n)
ans = []
f = [0] * n
for i in range(n):
	f[p[i]] += 1
for i in range(n - 1, 0, -1):
	f[p[i - 1]] += f[i]
pos = n - 1
ans = [[n, 1]]
while pos > 0:
	if p[pos] > 1:
		ans.append([p[pos], f[p[pos]] + 1])
	pos = p[pos] - 1
if len(s) > 1:
	f = s.count(s[0])
	if s[0] == s[len(s) - 1]:
		ans.append([1, f])
print(len(ans))
for i in sorted(ans):
	print(i[0], i[1])


s = input()
n = len(s)
p = [0] * n
k = 0
for i in range(1, n):
	while k != 0 and s[k] != s[i]:
		k = p[k - 1]
	if s[k] == s[i]:
		k += 1
	p[i] = k
a = []
k = n
while k != 0:
	a += [k]
	k = p[k - 1]
c = [0] * (n + 1)
for i in range(n):
	c[p[i]] += 1
for i in range(n - 1, 1, -1):
	c[p[i - 1]] += c[i]
print(len(a))
for t in reversed(a):
	print(t, c[t] + 1)


def z_advanced(s):
	Z = [0] * len(s)
	Z[0] = len(s)
	rt = 0
	lt = 0
	for k in range(1, len(s)):
		if k > rt:
			n = 0
			while n + k < len(s) and s[n] == s[n + k]:
				n += 1
			Z[k] = n
			if n > 0:
				lt = k
				rt = k + n - 1
		else:
			p = k - lt
			right_part_len = rt - k + 1
			if Z[p] < right_part_len:
				Z[k] = Z[p]
			else:
				i = rt + 1
				while i < len(s) and s[i] == s[i - k]:
					i += 1
				Z[k] = i - k
				lt = k
				rt = i - 1
	return Z

def kmptab(s):
	tab = [0] * len(s)
	i = 1
	j = 0
	while i < len(s):
		if s[i] == s[j]:
			tab[i] = j + 1
			i += 1
			j += 1
		elif j != 0:
			j = tab[j - 1]
		else:
			i += 1
	return tab

def __starting_point():
	s = input()
	tab = kmptab(s)
	my_set = set()
	i = len(s)
	while i != 0:
		my_set.add(i)
		i = tab[i - 1]
	V = []
	dict = {}
	for i in my_set:
		V.append(i)
		dict[i] = 0
	Z = z_advanced(s)
	v = []
	V.sort()
	my_tab = [0] * (len(s) + 1)
	for i in Z:
		my_tab[i] += 1
	somme = 0
	for i in range(len(my_tab) - 1, -1, -1):
		my_tab[i] += somme
		somme = my_tab[i]
	for i in dict:
		dict[i] = my_tab[i]
		v.append((dict[i], i))
	v.sort(key=lambda tup: tup[1])
	print(len(v))
	for i in v:
		print(str(i[1]) + ' ' + str(i[0]))
__starting_point()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
s = input()

def pi_func(s):
	pi = [0 for x in range(len(s))]
	for i in range(1, len(s)):
		l = pi[i - 1]
		while l > 0 and s[i] != s[l]:
			l = pi[l - 1]
		if s[i] == s[l]:
			l += 1
		pi[i] = l
	return pi
p = pi_func(s)
n = len(s)
ans = [0 for x in range(n + 1)]
for i in range(n):
	ans[p[i]] += 1
for i in reversed(range(1, n)):
	ans[p[i - 1]] += ans[i]
for i in range(n + 1):
	ans[i] += 1
suff = []
if len(p) >= 1:
	l = p[-1]
	suff.append(l)
	while l > 0:
		l = p[l - 1]
		suff.append(l)
sys.stdout.write(str(len(suff)) + '\n')
if suff[-1] == 0:
	suff.pop()
while suff:
	i = suff.pop()
	sys.stdout.write(str(i) + ' ' + str(ans[i]) + '\n')
sys.stdout.write(str(len(s)) + ' 1\n')


s = str(input())
lps = [0] * 100005
dp = [0] * 100005
ada = [0] * 100005
tunda = [0] * 100005
n = len(s)
i = 1
j = 0
lps[0] = 0
while i < n:
	if s[i] == s[j]:
		j += 1
		lps[i] = j
		i += 1
	elif j == 0:
		lps[i] = 0
		i += 1
	else:
		j = lps[j - 1]
for i in range(n - 1, -1, -1):
	tunda[i] += 1
	dp[lps[i]] += tunda[i]
	if lps[i]:
		tunda[lps[i] - 1] += tunda[i]
j = n
vector = []
while 1:
	vector.append((j, 1 + dp[j]))
	j = lps[j - 1]
	if j == 0:
		break
vector.reverse()
print(len(vector))
for i in vector:
	print(i[0], i[1])


import os
import sys
from io import BytesIO, IOBase
import heapq as h
import bisect
from types import GeneratorType
BUFSIZE = 8192

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
import collections as col
import math, string

def getInts():
	return [int(s) for s in input().split()]

def getInt():
	return int(input())

def getStrs():
	return [s for s in input().split()]

def getStr():
	return input()

def listStr():
	return list(input())
MOD = 10 ** 9 + 7
mod = 10 ** 9 + 7
t = 1
p = 10 ** 9 + 7

def ncr_util():
	inv[0] = inv[1] = 1
	fact[0] = fact[1] = 1
	for i in range(2, 300001):
		inv[i] = inv[i % p] * (p - p // i) % p
	for i in range(1, 300001):
		inv[i] = inv[i - 1] * inv[i] % p
		fact[i] = fact[i - 1] * i % p

def z_array(s1):
	n = len(s1)
	z = [0] * n
	(l, r, k) = (0, 0, 0)
	for i in range(1, n):
		if i > r:
			(l, r) = (i, i)
			while r < n and s1[r - l] == s1[r]:
				r += 1
			z[i] = r - l
			r -= 1
		else:
			k = i - l
			if z[k] < r - i + 1:
				z[i] = z[k]
			else:
				l = i
				while r < n and s1[r - l] == s1[r]:
					r += 1
				z[i] = r - l
				r -= 1
	return z

def solve():
	s1 = s + '#' + s
	z = z_array(s1)
	n = len(s1)
	d = {}
	d1 = {}
	ans = []
	for i in range(len(s), n):
		if z[i] != 0:
			if z[i] + i == n:
				d[z[i]] = d.get(z[i], 0) + 1
	z1 = z_array(s)
	l1 = []
	l1.append(len(s))
	d1[len(s)] = 1
	for i in range(len(z1)):
		if z1[i] > 0:
			d1[z[i]] = d1.get(z[i], 0) + 1
			l1.append(z[i])
	l1 = list(set(l1))
	l1.sort()
	ans.append([l1[-1], 1])
	for i in range(len(l1) - 2, -1, -1):
		d1[l1[i]] += d1[l1[i + 1]]
		if d.get(l1[i], -1) != -1:
			ans.append([l1[i], d1[l1[i]]])
	print(len(ans))
	for i in range(len(ans) - 1, -1, -1):
		print(ans[i][0], ans[i][1])
for _ in range(t):
	s = input()
	solve()


import heapq
from bisect import bisect_left, bisect_right, insort
from collections import Counter
from collections import OrderedDict
from collections import deque
from itertools import accumulate, product
import math
R = lambda : map(int, input().split())
s = input()
(l, r, z) = (0, 0, [0] * len(s))
for i in range(1, len(s)):
	if i > r - 1:
		l = r = i
		while r < len(s) and s[r] == s[r - i]:
			r += 1
		z[i] = r - l
	elif z[i - l] < r - i:
		z[i] = z[i - l]
	else:
		l = i
		while r < len(s) and s[r] == s[r - i]:
			r += 1
		z[i] = r - l
sz = sorted(z[:])
res = []
for i in range(len(s) - 1, 0, -1):
	if z[i] == len(s) - i:
		res.append((z[i], len(sz) - bisect_left(sz, z[i])))
print(len(res) + 1)
for x in res:
	print(x[0], x[1] + 1)
print(len(s), 1)


import sys
input = sys.stdin.readline
from collections import deque
S = input().strip()
LEN = len(S)
i = 1
j = 0
A = [0] * LEN
A[0] = LEN
while i < LEN:
	while i + j < LEN and S[j] == S[i + j]:
		j += 1
	A[i] = j
	if j == 0:
		i += 1
		continue
	k = 1
	while i + k < LEN and k + A[k] < j:
		A[i + k] = A[k]
		k += 1
	i += k
	j -= k
ANS = [0] * (LEN + 1)
for a in A:
	ANS[a] += 1
for i in range(LEN - 1, -1, -1):
	ANS[i] += ANS[i + 1]
ANS2 = []
for i in range(1, LEN + 1):
	if A[LEN - i] == i:
		ANS2.append((i, ANS[i]))
print(len(ANS2))
for (x, y) in ANS2:
	print(x, y)


def zeta(s):
	n = len(s)
	z = [0] * n
	(l, r) = (0, 0)
	for i in range(1, n):
		if i <= r:
			z[i] = min(r - i + 1, z[i - l])
		while i + z[i] < n and s[z[i]] == s[i + z[i]]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z
s = input()
n = len(s)
z = zeta(s)
l = [0] * n
for i in z:
	l[i] += 1
cum = [l[-1]]
for i in range(n - 2, -1, -1):
	cum.append(l[i] + cum[-1])
cum = cum[::-1]
ans = [(n, 1)]
for i in range(n - 1, 0, -1):
	if i + z[i] == n:
		ans.append((n - i, cum[n - i] + 1))
print(len(ans))
for i in sorted(ans):
	print(*i)


import os
import sys
from io import BytesIO, IOBase

def main():
	txt = input()
	n = len(txt)
	zz = n
	string = txt + '$' + txt
	n += n + 1
	z = [0] * n

	def makeZarray():
		(l, r, k) = (0, 0, 0)
		for i in range(1, n):
			if i > r:
				(l, r) = (i, i)
				while r < n and string[r - l] == string[r]:
					r += 1
				r -= 1
				z[i] = r - l + 1
			else:
				k = i - l
				if z[k] + i > r:
					l = i
					while r < n and string[r - l] == string[r]:
						r += 1
					r -= 1
					z[i] = r - l + 1
				else:
					z[i] = z[k]
	makeZarray()
	touse = set()
	ans = [0] * (zz + 1)
	for i in range(n - 1, zz, -1):
		if z[i] + i == n:
			touse.add(z[i])
		ans[z[i]] += 1
	for i in range(zz, 0, -1):
		ans[i - 1] += ans[i]
	print(len(touse))
	l = list(touse)
	l.sort()
	for item in l:
		print(item, ans[item])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


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

def solve(s):
	n = len(s)
	pi = prefix_function(s)
	j = n
	prefixes = []
	while j:
		prefixes.append(j)
		j = pi[j - 1]
	print(len(prefixes))
	if len(prefixes) == 1:
		print(n, 1)
		return
	cnt = [0] * (n + 1)
	for i in range(n):
		cnt[pi[i]] += 1
	for i in range(n - 1, 0, -1):
		cnt[pi[i - 1]] += cnt[i]
	for i in range(n + 1):
		cnt[i] += 1
	for i in reversed(prefixes):
		print(i, cnt[i])

def main():
	s = input()
	solve(s)
main()


s = input()
n = len(s)
p = [0] * (n + 1)
ans = [0] * (n + 1)
j = 0
li = [n]
for i in range(1, n):
	while j > 0 and s[i] != s[j]:
		j = p[j - 1]
	if s[i] == s[j]:
		j += 1
	p[i] = j
for i in range(0, n):
	ans[p[i]] += 1
for i in range(n - 1, -1, -1):
	ans[p[i - 1]] += ans[i]
for i in range(0, n + 1):
	ans[i] += 1
j = n - 1
while j > 0:
	if p[j]:
		li.append(p[j])
	j = p[j] - 1
li.reverse()
print(len(li))
for i in range(0, len(li)):
	print(li[i], ans[li[i]])


import os, sys
from io import BytesIO, IOBase

def zArray(string):
	n = len(string)
	(Z, l, r) = ([0] * n, 0, 0)
	for i in range(1, n):
		val = Z[i - l]
		if i + val >= r:
			val = max(r - i, 0)
			while i + val < n and string[val] == string[i + val]:
				val += 1
			(l, r) = (i, i + val)
		Z[i] = val
	Z[0] = n
	return Z

def main():
	s = input().strip()
	n = len(s)
	Z = zArray(s)
	val = [0] * (n + 1)
	for i in Z:
		val[i] += 1
	for i in range(n - 1, -1, -1):
		val[i] += val[i + 1]
	(le, freq) = ([], [])
	for i in range(n):
		if Z[i] == n - i:
			le.append(n - i)
			freq.append(val[n - i])
	print(len(le))
	for i in range(len(le) - 1, -1, -1):
		print(le[i], freq[i])
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def preZ(s):
	n = len(s)
	z = [0] * n
	z[0] = n
	r = 0
	if n == 1:
		return z
	while r + 1 < n and s[r] == s[r + 1]:
		r += 1
	z[1] = r
	l = 1 if r > 0 else 0
	for k in range(2, n):
		bl = r + 1 - k
		gl = z[k - l]
		if gl < bl:
			z[k] = z[k - l]
		else:
			j = max(0, r - k + 1)
			while k + j < n and s[j] == s[k + j]:
				j += 1
			z[k] = j
			(l, r) = (k, k + j - 1)
	return z

def f(s):
	n = len(s)
	c = [0] * (n + 1)
	b = [False] * (n + 1)
	z = preZ(s)
	for i in range(n):
		t = z[i]
		b[t] = b[t] or z[i] + i == n
		c[t] += 1
	for t in range(n - 1, 0, -1):
		c[t] += c[t + 1]
	return '\n'.join(['%d' % sum(b)] + ['%d %d' % (t, c[t]) for t in range(1, n + 1) if b[t]])
print(f(input()))


s = str(input())
n = len(s)
z = [0]
li = [-1]
d = dict()
ans = set()
lis = []

def zf(s):
	l = r = 0
	for i in range(1, n):
		z.append(0)
		if i <= r:
			z[-1] = min(z[i - l], r - i + 1)
		while i + z[i] < n and s[i + z[i]] == s[z[i]]:
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
		li.append(z[i])
		if z[i] + i == n:
			ans.add(z[i])
zf(s)
li.sort()
x = 1
for i in range(1, len(li)):
	if li[i] == li[i - 1]:
		x += 1
	else:
		d.update({li[i - 1]: x})
		x = 1
d.update({li[-1]: x})
x = len(li) + 1
for i in d:
	x -= d[i]
	d[i] += x
print(len(ans) + 1)
for i in ans:
	lis.append((i, d[i]))
lis.sort()
for i in lis:
	print(i[0], i[1])
print(n, 1)


from itertools import accumulate

def z_algorithm(s):
	n = len(s)
	(l, d) = (1, 0)
	ans = [0] * n
	ans[0] = n
	while l < n:
		while l + d < n and s[d] == s[l + d]:
			d += 1
		ans[l] = d
		if d == 0:
			l += 1
			continue
		k = 1
		while l + k < n and k + ans[k] < d:
			ans[l + k] = ans[k]
			k += 1
		l += k
		d -= k
	return ans
z = z_algorithm(input())
n = len(z)
ct = [0] * (n + 1)
match = [False] * (n + 1)
for (i, v) in enumerate(z):
	ct[v] += 1
	match[n - i] = n - i == v
for i in range(n - 1, -1, -1):
	ct[i] += ct[i + 1]
buf = []
for (i, v) in enumerate(ct):
	if i > 0 and v > 0 and match[i]:
		buf.append('{} {}'.format(i, v))
print(len(buf))
print('\n'.join(buf))


def compute_z(data):
	z = [0 for _ in range(len(data))]
	z[0] = len(data)
	l = 0
	r = 0
	for i in range(1, len(data)):
		if i <= r:
			z[i] = min(z[i - l], r - i + 1)
		while i + z[i] < len(data) and data[z[i]] == data[i + z[i]]:
			z[i] += 1
		if i + z[i] - 1 > r:
			r = i + z[i] - 1
			l = i
	return z
data = input()
n = len(data)
z = compute_z(data)
feq_z = [0 for _ in range(n)]
for value in z:
	if value == 0:
		continue
	index = value - 1
	feq_z[index] += 1
for i in range(n - 2, -1, -1):
	feq_z[i] += feq_z[i + 1]
count = 0
for i in range(n - 1, -1, -1):
	if z[i] == n - i:
		count += 1
print(count)
for i in range(n - 1, -1, -1):
	if z[i] == n - i:
		print('{} {}'.format(z[i], feq_z[z[i] - 1]))