For two strings A and B, we define the similarity of the strings to be the length of the longest prefix common to both strings. For example, the similarity of strings "abc" and "abd" is 2, while the similarity of strings "aaa" and "aaab" is 3.

Calculate the sum of similarities of a string S with each of it's suffixes.

Input Format

The first line contains the number of test cases t. 

Each of the next t lines contains a string to process, $\boldsymbol{\mathrm{~S~}}$.

Constraints

$1\leq t\leq10$    
$1\leq|s|\leq1000000$  
$\boldsymbol{\mathrm{~S~}}$ is composed of characters in the range ascii[a-z]  

Output Format

Output t lines, each containing the answer for the corresponding test case.

Sample Input
2
ababaa  
aa

Sample Output
11  
3

Explanation

For the first case, the suffixes of the string are "ababaa", "babaa", "abaa", "baa", "aa" and "a". The similarities of these strings with the string "ababaa" are 6,0,3,0,1, & 1 respectively. Thus, the answer is 6 + 0 + 3 + 0 + 1 + 1 = 11.

For the second case, the answer is 2 + 1 = 3.

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for i in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


def similarity(st):
	rt = [len(st)]
	i = 1
	(f, fi) = (0, 0)
	k = 0
	while i < len(st):
		if fi < i < fi + f:
			if rt[i - fi] >= fi + f - i:
				k = fi + f - i
				(f, fi) = (0, 0)
			else:
				rt.append(rt[i - fi])
				i += 1
				k = 0
		else:
			while i + k < len(st) and st[k] == st[i + k]:
				k += 1
			rt.append(k)
			(f, fi) = (k, i)
			i += 1
			k = 0
	return sum(rt)
for i in range(int(input())):
	print(similarity(input().strip()))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


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

def suffix_sim(s):
	z = compute_z(s)
	return sum(z)
n = int(input())
for i in range(0, n):
	print(suffix_sim(input().rstrip()))


def naive(S):
	simsum = 0
	for i in range(len(S)):
		simsum += similarity(S, S[i:])
	return simsum

def similarity(S1, S2):
	c = 0
	for i in range(min(len(S1), len(S2))):
		if S1[i] == S2[i]:
			c += 1
		else:
			break
	return c

def z(s):
	l = r = 0
	n = len(s)
	z = [0 for _ in range(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
	return sum(z)
ncases = int(input())
for _ in range(ncases):
	S = input().strip()
	print(z(S) + len(S))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


def trivial_prefix(s_1, s_2):
	N_1 = len(s_1)
	N_2 = len(s_2)
	N = min(N_1, N_2)
	i = 0
	if s_1[0] != s_2[0]:
		return 0
	while i < N and s_1[i] == s_2[i]:
		i += 1
	return i
t = int(input())
for i in range(t):
	s = input().strip()
	N = len(s)
	z = []
	for i in range(N):
		z.append(0)
	r = 0
	l = 0
	num = 0
	z[0] = N
	for i in range(1, N):
		if i > r:
			test = trivial_prefix(s[i:], s)
			z[i] = test
			if test != 0:
				l = i
				r = test + i - 1
		elif z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			z[i] = r - i
			num_1 = trivial_prefix(s[r:], s[r - i:])
			z[i] = z[i] + num_1
			l = i
			r = r + num_1 - 1
	for i in range(N):
		num += z[i]
	print(num)


class ZBox:

	def __init__(self, left=0, right=0):
		self.left = left
		self.right = right

	def project_box(self, string):
		return string[self.right - self.left]

	def adjust_box(self, string):
		string_len = len(string)
		while self.right < string_len and self.project_box(string) == string[self.right]:
			self.right += 1

	def set_both(self, value):
		self.left = self.right = value

def z_algorithm(string):
	string_len = len(string)
	if string_len <= 0:
		return []
	z_arr = [0] * string_len
	z_arr[0] = string_len
	zbox = ZBox(0, 0)
	for ind in range(1, string_len):
		if ind > zbox.right:
			zbox.set_both(ind)
			zbox.adjust_box(string)
			z_arr[ind] = zbox.right - zbox.left
			zbox.right -= 1
		else:
			k = ind - zbox.left
			if z_arr[k] < zbox.right - ind + 1:
				z_arr[ind] = z_arr[k]
			else:
				zbox.left = ind
				zbox.adjust_box(string)
				z_arr[ind] = zbox.right - zbox.left
				zbox.right -= 1
	return z_arr

def process_input():
	num_test_cases = int(input().strip())
	for i in range(num_test_cases):
		string = input().strip().lower()
		print(sum(z_algorithm(string)))

def main():
	process_input()
main()


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

def getStringSimilarity(s):
	z = getZFunctionArray(s)
	return sum(z) + len(s)
t = int(input().strip())
for _t in range(t):
	s = input().strip()
	print(getStringSimilarity(s))


import sys

def string_similarity(s):
	(l, r, n) = (0, 0, len(s))
	z = [0] * n
	for i in range(1, n):
		if i <= r and z[i - l] < r - i + 1:
			z[i] = z[i - l]
		else:
			l = i
			if i > r:
				r = i
			while r < n and s[r - l] == s[r]:
				r += 1
			z[i] = r - l
			r -= 1
	return n + sum(z)
T = int(sys.stdin.readline())
for _ in range(T):
	print(string_similarity(sys.stdin.readline().strip()))


def Zfunction(s):
	similar_chars = 0
	l = len(s)
	z = [0] * l
	(left, right) = (0, 0)
	for i in range(1, l):
		if i <= right:
			z[i] = min(z[i - left], right - i + 1)
		while i + z[i] < l and s[z[i]] == s[i + z[i]]:
			z[i] += 1
		if i + z[i] - 1 > right:
			left = i
			right = i + z[i] - 1
	return l + sum(z)
T = int(input())
for _ in range(T):
	s = input().strip()
	print(Zfunction(s))


def stringSimilarity(loopStr, strcomparator):
	n = len(loopStr)
	z = [int(0) for i in range(n)]
	l = 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 strcomparator(loopStr[z[i]], loopStr[i + z[i]]):
			z[i] += 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return sum(z) + n
t = int(input())
for i in range(0, t):
	loopStr = ''.join(map(str, input().strip().split()))
	print(stringSimilarity(loopStr, lambda x, y: x == y))


import sys
import operator

def zfunction(s):
	lens = len(s)
	z = [0 for i in range(0, lens)]
	l = 0
	r = 0
	for i in range(1, lens):
		if i <= r:
			z[i] = min(r - i + 1, z[i - l])
		while i + z[i] < lens and s[z[i]] == s[i + z[i]]:
			z[i] = z[i] + 1
		if i + z[i] - 1 > r:
			l = i
			r = i + z[i] - 1
	return z
t = int(input().strip())
for i in range(0, t):
	s = input().strip()
	print(len(s) + sum(zfunction(s)))


def compute_z(string):
	n = len(string)
	z = [n]
	L = R = 0
	for i in range(1, n):
		if i > R:
			L = R = i
			while R < n and string[R - L] == string[R]:
				R += 1
			z.append(R - L)
			R -= 1
		else:
			k = i - L
			if z[k] < R - i:
				z.append(z[k])
			else:
				L = i
				while R < n and string[R - L] == string[R]:
					R += 1
				z.append(R - L)
				R -= 1
	return z
n = int(input().strip())
for a0 in range(n):
	s = input().strip()
	print(sum(compute_z(s)))


import sys

def linear_z_array(givenstr):
	strlen = len(givenstr)
	z = [0] * strlen
	lbound = 0
	rbound = 0
	for i in range(1, strlen):
		if i > rbound:
			lbound = rbound = i
			while rbound < strlen and givenstr[rbound - lbound] == givenstr[rbound]:
				rbound += 1
			z[i] = rbound - lbound
			rbound -= 1
		else:
			k = i - lbound
			if z[k] < rbound - i + 1:
				z[i] = z[k]
			else:
				lbound = i
				while rbound < strlen and givenstr[rbound - lbound] == givenstr[rbound]:
					rbound += 1
				z[i] = rbound - lbound
				rbound -= 1
	return z
cases = int(input().strip())
for _ in range(cases):
	givenstr = input().strip()
	z = linear_z_array(givenstr)
	print(str(sum(z) + len(z)))


def stringSimilarity(a):
	ans = 0
	z = z_advanced(a)
	for zval in z:
		ans += zval
	return ans

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
t = int(input())
for i in range(0, t):
	a = input().strip()
	print(stringSimilarity(a))


def stringSimilarity(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
	f = 0
	for x in range(0, len(Z)):
		f = f + Z[x]
	return f
t = int(input().strip())
ANSWER = []
for a0 in range(t):
	a = input().strip()
	result = stringSimilarity(a)
	ANSWER.append(result)
for x in range(0, t):
	print(ANSWER[x])


import sys

def stringSimilarity(alt):
	z = [len(alt)] + [0] * (len(alt) - 1)
	left = 0
	right = 0
	for k in range(1, len(alt)):
		if k > right:
			left = right = k
			while right < len(alt) and alt[right] == alt[right - left]:
				right += 1
			z[k] = right - left
			right -= 1
		else:
			k1 = k - left
			if z[k1] < right - k + 1:
				z[k] = z[k1]
			else:
				left = k
				while right < len(alt) and alt[right] == alt[right - left]:
					right += 1
				z[k] = right - left
				right -= 1
		k += 1
	return sum(z)
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	result = stringSimilarity(s)
	print(result)


import sys

def stringSimilarity(s):
	return sum(calculate_z_function(s)) + len(s)

def calculate_z_function(s):
	right = 0
	left = 0
	M = len(s)
	z = [0] * M
	for k in range(1, M):
		if k > right:
			left = right = k
			while right < M and s[right] == s[right - left]:
				right += 1
			z[k] = right - left
			right -= 1
		else:
			k1 = k - left
			if z[k1] < right - k + 1:
				z[k] = z[k1]
			else:
				left = k
				while right < M and s[right] == s[right - left]:
					right += 1
				z[k] = right - left
				right -= 1
	return z
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	result = stringSimilarity(s)
	print(result)


import sys

def stringSimilarity(s):
	result = length = len(s)
	right = 0
	left = 0
	z = [length]
	for i in range(1, length):
		z.append(0)
		if i <= right:
			z[i] = min(right - i + 1, z[i - left])
		while i + z[i] < length and s[z[i]] == s[i + z[i]]:
			z[i] += 1
		if i + z[i] - 1 > right:
			left = i
			right = i + z[i] - 1
		result += z[i]
	return result
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	result = stringSimilarity(s)
	print(result)


import sys

def stringSimilarity(s):
	total = len(s)
	n = total
	z = [0] * n
	z[0] = 0
	l = 0
	r = 0
	for i in range(1, n):
		z[i] = 0
		if i <= r:
			z[i] = min(z[i - l], r - i + 1)
		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
		total += z[i]
	return total
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	result = stringSimilarity(s)
	print(result)


import sys

def stringSimilarity(string):
	n = len(string)
	z = [0] * n
	(zbox_l, zbox_r, z[0]) = (0, 0, n)
	for i in range(1, n):
		if i < zbox_r:
			k = i - zbox_l
			if z[k] < zbox_r - i:
				z[i] = z[k]
				continue
			zbox_l = i
		else:
			zbox_l = zbox_r = i
		while zbox_r < n and string[zbox_r - zbox_l] == string[zbox_r]:
			zbox_r += 1
		z[i] = zbox_r - zbox_l
	return sum(z)
t = int(input().strip())
for a0 in range(t):
	s = input().strip()
	result = stringSimilarity(s)
	print(result)


import sys

def stringSimilarity(s):
	l = r = 0
	z = []
	for i in range(len(s)):
		z.append(0)
	for i in range(1, len(s)):
		if i <= r:
			z[i] = min(r - i + 1, z[i - l])
		while i + z[i] < len(s) 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 sum(z) + len(s)
t = int(input().strip())
for a0 in range(t):
	s = input().strip().strip('\n')
	result = stringSimilarity(s)
	print(result)


def compute_prefix_array(prefix):
	result = [0] * len(prefix)
	matched = 0
	for i in range(1, len(prefix)):
		while matched > 0 and prefix[matched] != prefix[i]:
			matched = result[matched - 1]
		if prefix[matched] == prefix[i]:
			matched += 1
		result[i] = matched
	return result

def sum_suffix_similarities(s):
	prefix_array = compute_prefix_array(s)
	sum_array = []
	count = len(s)
	for i in range(len(s)):
		if prefix_array[i]:
			prefix_array[i] = prefix_array[prefix_array[i] - 1] + 1
		sum_array.append(prefix_array[i])
		count += sum_array[-1]
	return count
test_cases = int(input().strip())
for _ in range(test_cases):
	print(sum_suffix_similarities(input().strip()))