Read problems statements in Mandarin Chinese . 

You are given two strings A and B of the same length. Each string contains N Lower case Latin character (from 'a' to 'z'). A shift operation will remove the first character of a string and add the same character at the end of that string. For example after you perform a shift operation on a string 'abcd', the new string will be 'bcda'. If you perform this operation two times, the new string will be 'cdab'. You need to use some (maybe none) shift operations on the string B to maximize the length of the longest common prefix of A and B. If more than one result can be found pick the one that use smallest number of shift operations.

------ Input ------ 

The first line of the input contains a single integer N. The second and the third lind contains the string A and B respectively.
 
------ Output ------ 

Contains a single integer which is the number of shift operations.
 
------ Constraints ------ 

30 points:
$1 ≤ N ≤ 5000$
30 points:
$1 ≤ N ≤ 10^{4}$
40 points:
$1 ≤ N ≤ 10^{6}$

----- Sample Input 1 ------ 
5
ccadd
bddcc
----- Sample Output 1 ------ 
3

Difficulty: HARD
Tags: String algorithms

Starter code:

Solutions:
n = int(input())
s1 = input()
s2 = input()
s2 += s2
first = 0
second = n - 1
op = 0
while first <= second:
	m = (first + second) // 2
	c = s1[:m + 1]
	x = s2.find(c)
	if x == -1:
		second = m - 1
	else:
		first = m + 1
	if op < x:
		op = x
print(op)


def tashift(a, B, l, r, x, lst):
	while l <= r:
		m = (l + r) // 2
		c = a[:m + 1]
		y = B.find(c)
		if y == -1:
			r = m - 1
		else:
			l = m + 1
		if x < y:
			x = y
	lst.append(x)
n = int(input())
a = input()
b = input()
B = b + b
lst = []
l = 0
r = n - 1
x = 0
tashift(a, B, l, r, x, lst)
for i in lst:
	print(i, end='')
	print()


n = int(input())
a = input()
b = input()
(lo, hi) = (0, n - 1)
res = '#'
while lo <= hi:
	mid = (lo + hi) // 2
	if a[:mid + 1] in b:
		res = a[:mid + 1]
		lo = mid + 1
	else:
		hi = mid - 1
print(b.index(res))


def findPi(str1, pi, m):
	i = 0
	pi[0] = 0
	j = 1
	while j < m:
		if str1[i] == str1[j]:
			i += 1
			pi[j] = i
			j += 1
		elif i == 0:
			pi[j] = i
			j += 1
		else:
			i = pi[i - 1]
	return pi

def find(pi_1, str1, str2):
	m = len(str1)
	n = len(str2)
	pi_2 = [0] * n
	i = 0
	j = 0
	while i < m and j < n:
		if str1[i] == str2[j]:
			i += 1
			pi_2[j] = i
			j += 1
		elif i == 0:
			j += 1
		else:
			i = pi_1[i - 1]
	val = max(pi_2)
	pos = pi_2.index(val)
	return pos - val + 1
t = int(input())
str1 = list(input())
str2 = list(input())
m = len(str1)
n = len(str2)
pi_1 = [None] * m
pi_1 = findPi(str1, pi_1, m)
print(find(pi_1, str1, str2))


n = int(input())
A = input()
B = input()

def computeTemporaryArray(pattern):
	lps = [0] * len(pattern)
	index = 0
	for i in range(1, len(pattern)):
		if pattern[i] == pattern[index]:
			lps[i] = index + 1
			index += 1
		elif index != 0:
			index = lps[index - 1]
		else:
			lps[i] = 0
	return lps

def KMP(strr, pattern):
	lps = computeTemporaryArray(pattern)
	(i, j) = (0, 0)
	(max_j, max_rotations) = (0, 0)
	while i < len(strr) and j < len(pattern):
		if strr[i] == pattern[j]:
			i += 1
			j += 1
		elif j != 0:
			j = lps[j - 1]
		else:
			i += 1
		if j > max_j:
			max_j = j
			max_rotations = max(max_rotations, i - len(pattern) - j if i > len(pattern) else i - j)
	return max_rotations
strr = B + B
pattern = A
result = KMP(strr, pattern)
print(result)


n = int(input())
a = input()
B = input()
b = B + B
l = 0
r = n - 1
x = 0
while l <= r:
	m = (l + r) // 2
	c = a[:m + 1]
	y = b.find(c)
	if y == -1:
		r = m - 1
	else:
		l = m + 1
	if x < y:
		x = y
print(x)


def createLPS(pattern):
	j = 0
	lps = [0]
	i = 1
	while i < len(pattern):
		if pattern[i] == pattern[j]:
			i += 1
			j += 1
			lps.append(j)
		elif j == 0:
			i += 1
			lps.append(0)
		else:
			j = lps[j - 1]
	return lps

def KMPStringsearch(s, pattern):
	lps = createLPS(pattern)
	i = 0
	j = 0
	maxMatch = 0
	currShift = -1
	while i < len(s) and j < len(pattern):
		if s[i] == pattern[j]:
			i += 1
			j += 1
			if j > maxMatch:
				maxMatch = j
				currShift = i - j
		elif j != 0:
			j = lps[j - 1]
		else:
			i += 1
		if j == len(pattern):
			break
	return currShift
n = int(input())
pattern = input()
s = input()
print(KMPStringsearch(s, pattern))


n = int(input())
a = input()
B = input()
b = B + B
var1 = 0
var2 = n - 1
x = 0
while var1 <= var2:
	m = (var1 + var2) // 2
	c = a[:m + 1]
	y = b.find(c)
	if y == -1:
		var2 = m - 1
	else:
		var1 = m + 1
	if x < y:
		x = y
print(x)


n = int(input())
a = input()
c = input()
b = c + c
res = 0
left = 0
right = n - 1
while left <= right:
	mid = int((left + right) / 2)
	d = a[:mid + 1]
	ans = b.find(d)
	if ans == -1:
		right = mid - 1
	else:
		left = mid + 1
	if res < ans:
		res = ans
print(res)


def computelps(pat, m, lps):
	le = 0
	lps[0] = 0
	i = 1
	while i < m:
		if pat[i] == pat[le]:
			le += 1
			lps[i] += le
			i += 1
		elif le > 0:
			le = lps[le - 1]
		else:
			lps[i] = 0
			i += 1

def kmp(pat, txt):
	n = len(txt)
	m = len(pat)
	lps = [0] * m
	computelps(pat, m, lps)
	(i, j) = (0, 0)
	(ma, ans, res) = (0, 0, 0)
	while i < n:
		if pat[j] == txt[i]:
			i += 1
			j += 1
			ma += 1
		if ma > res:
			res = ma
			ans = i - j
		if j == m:
			break
		elif i < n and pat[j] != txt[i]:
			ma = 0
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
	print(ans)
n = int(input())
a = input()
b = input()
b = b + b
kmp(a, b)


from bisect import *
from collections import *
from itertools import *
import functools
import sys
import math
from decimal import *
from copy import *
from heapq import *
getcontext().prec = 30
MAX = sys.maxsize
MAXN = 10 ** 6 + 1
MOD = 10 ** 9 + 7

def isprime(n):
	n = abs(int(n))
	if n < 2:
		return False
	if n == 2:
		return True
	if not n & 1:
		return False
	for x in range(3, int(n ** 0.5) + 1, 2):
		if n % x == 0:
			return False
	return True

def mhd(a, b):
	return abs(a[0] - b[0]) + abs(b[1] - a[1])

def charIN(x=' '):
	return sys.stdin.readline().strip().split(x)

def arrIN(x=' '):
	return list(map(int, sys.stdin.readline().strip().split(x)))

def eld(x, y):
	a = y[0] - x[0]
	b = x[1] - y[1]
	return (a * a + b * b) ** 0.5

def lgcd(a):
	g = a[0]
	for i in range(1, len(a)):
		g = math.gcd(g, a[i])
	return g

def ms(a):
	msf = -MAX
	meh = 0
	st = en = be = 0
	for i in range(len(a)):
		meh += a[i]
		if msf < meh:
			msf = meh
			st = be
			en = i
		if meh < 0:
			meh = 0
			be = i + 1
	return (msf, st, en)

def ncr(n, r):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % MOD
		den = den * (i + 1) % MOD
	return num * pow(den, MOD - 2, MOD) % MOD

def flush():
	return sys.stdout.flush()

def fac(n):
	ans = 1
	for i in range(1, n + 1):
		ans *= i
		ans %= MOD
	return ans
n = int(input())
a = input().strip()
b = input().strip()
b += b
i = 0
mx = 0
op = 0
st = 0
while i < n:
	if b[i] == a[0]:
		st = i
		c = 0
		for j in range(n):
			if a[j] == b[i]:
				c += 1
				i += 1
			else:
				break
		if c > mx:
			mx = c
			op = st
	else:
		i += 1
print(op)


def LPS(s):
	lps = [0 for i in range(len(s))]
	for i in range(1, len(s)):
		j = i - 1
		while j >= 0 and s[lps[j]] != s[i]:
			j = lps[j] - 1
		if j >= 0:
			lps[i] = lps[j] + 1
	return lps
N = int(input())
A = input()
B = input()
lpsA = LPS(A)
a = 0
b = 0
shifts = 0
curShift = 0
longPref = 0
while curShift < N:
	while a < len(A) and b < len(B) and (A[a] == B[b]):
		a += 1
		b += 1
	assert a < len(A) and b < len(B) or (a == len(A) and b == len(B))
	if a > longPref:
		shifts = curShift
		longPref = a
	if a == 0:
		B += B[b]
		curShift += 1
		b += 1
	elif a == len(A):
		break
	else:
		B += B[b - a:b - lpsA[a - 1]]
		curShift += a - lpsA[a - 1]
		a = lpsA[a - 1]
print(shifts)


def lpsarr(pat, m, lps):
	len = 0
	i = 1
	lps[0] = 0
	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

def kmpsearch(pat, txt):
	n = len(txt)
	m = len(pat)
	lps = [0] * m
	lpsarr(pat, m, lps)
	i = 0
	j = 0
	(max, ans, res) = (0, 0, 0)
	while i < n:
		if pat[j] == txt[i]:
			i += 1
			j += 1
			max += 1
		if max > res:
			res = max
			ans = i - j
		if j == m:
			break
		elif i < n and pat[j] != txt[i]:
			max = 0
			if j != 0:
				j = lps[j - 1]
			else:
				i += 1
	print(ans)
n = int(input())
a = input()
b = input()
b = b + b
kmpsearch(a, b)


l = int(input())
s1 = input()
s2 = input()
s2 += s2
n1 = 0
n2 = l - 1
shift = 0
while n1 <= n2:
	m = (n1 + n2) // 2
	c = s1[:m + 1]
	y = s2.find(c)
	if y == -1:
		n2 = m - 1
	else:
		n1 = m + 1
	if shift < y:
		shift = y
print(shift)


from math import *
from collections import *
from functools import *

def rvi():
	return [*map(int, input().split())]

def ri():
	return int(input())
input()
w = input()
t = input() * 2
i = 0
j = -1
lps = [-1] * (len(w) + 1)
while i < len(w):
	while j >= 0 and w[i] != w[j]:
		j = lps[j]
	i += 1
	j += 1
	lps[i] = j
i = 0
j = 0
(max_j, max_i) = (0, 0)
while i < len(t):
	while j >= 0 and t[i] != w[j]:
		j = lps[j]
	i += 1
	j += 1
	if j > max_j:
		max_j = j
		max_i = i - j
	elif j == max_j:
		max_i = min(i - j, max_i)
print(max_i)


def computeLps(pattern, n):
	lps = [0 for i in range(n)]
	j = 0
	i = 1
	while i < n:
		if pattern[i] == pattern[j]:
			j += 1
			lps[i] = j
			i += 1
		elif j == 0:
			lps[i] = 0
			i += 1
		else:
			j = lps[j - 1]
	return lps

def determineAnswer(pattern, string, n):
	lps = computeLps(pattern, n)
	i = 0
	j = 0
	ind = -1
	min = 0
	for prefixLength in range(1, n + 1):
		flag = False
		while i < n:
			if pattern[j] == string[i]:
				i += 1
				j += 1
			elif i < n:
				if j != 0:
					j = lps[j - 1]
				else:
					i += 1
			if j == prefixLength:
				flag = True
				ind = i - j
				break
		if flag == False:
			break
		else:
			min = ind
	return min
n = int(input())
pattern = input()
string = input()
minShifts = determineAnswer(pattern, string, n)
print(minShifts)


import sys
n = int(input())
a = input()
b = input()
lps = [0] * n
i = 1
temp = 0
while i < n:
	if a[i] == a[temp]:
		temp += 1
		lps[i] = temp
		i += 1
	elif temp != 0:
		temp = lps[temp - 1]
	else:
		lps[i] = 0
		i += 1
i = 0
j = 0
res = 0
temp = 0
b = b + b
maxi = -1
while i < len(b) and j < n:
	if b[i] == a[j]:
		temp += 1
		i += 1
		j += 1
	else:
		if temp > maxi:
			maxi = temp
			res = i - j
		if j == 0:
			i += 1
			temp = 0
		else:
			j = lps[j - 1]
			temp = 0
print(res)


try:
	T = int(input())
	f = input()
	s = input()
	(lo, hi) = (0, T - 1)
	res = '#'
	while lo <= hi:
		mid = (lo + hi) // 2
		if f[:mid + 1] in s:
			res = f[:mid + 1]
			lo = mid + 1
		else:
			hi = mid - 1
	print(s.index(res))
except:
	pass


def get_table(length, string):
	table = []
	table.append(0)
	j = 0
	for i in range(1, length):
		if string[i] == string[j]:
			table.append(table[i - 1] + 1)
			j += 1
		else:
			table.append(0)
			j = 0
	return table

def kmpModified(length, first, second):
	table = get_table(length, first)
	j = 0
	longestShift = 0
	longestMatch = 0
	for i in range(length * 2):
		if second[i] == first[j]:
			j += 1
			if j == length:
				return i - j + 1
		else:
			if longestMatch < j:
				longestMatch = j
				longestShift = i - j
			while j != 0:
				j = table[j - 1]
				if second[i] == first[j]:
					j += 1
					break
	if i == length * 2 - 1:
		if longestMatch < j:
			return i - j
	return longestShift

def main():
	length = int(input())
	first = input()
	second = input()
	second = second + second
	print(kmpModified(length, first, second))
main()


n = int(input())
a = input()
b = input()
f = 0
s = n - 1
op = 0
while f <= s:
	m = (f + s) // 2
	c = a[:m + 1]
	x = b.find(c)
	if x == -1:
		s = m - 1
	else:
		f = m + 1
	if op < x:
		op = x
print(op)


n = int(input())
a = input()
b = input()
b = b + b
n0 = n // 2
n1 = n0 // 2
while n1:
	idx = b.find(a[:n0])
	if idx >= 0:
		n0 += n1
	else:
		n0 -= n1
	n1 //= 2
while b.find(a[:n0]) < 0:
	n0 -= 1
print(b.find(a[:n0]))


n = int(input())
a = input()
B = input()
b = B + B
n1 = 0
n2 = n - 1
x = 0
cmp = []
while n1 <= n2:
	m = (n1 + n2) // 2
	c = a[:m + 1]
	y = b.find(c)
	if y == -1:
		n2 = m - 1
	else:
		n1 = m + 1
		cmp.append(y)
	if x < y:
		x = y
print(x)


No = int(input(''))
a = input('')
b = input('')
max_count = 0
max_shift = 0
i = 0
while i < No:
	count = 0
	j = 0
	while j < No and a[j] == b[(j + i) % No]:
		count += 1
		j += 1
	if max_count < count:
		max_count = count
		max_shift = i
	if j > 0:
		i += count
	else:
		i += 1
print(max_shift)


t = int(input())
list = []
a = input()
b = input()
(low, high) = (0, t - 1)
rpp = '#'
while low <= high:
	mid = (low + high) // 2
	if a[:mid + 1] in b:
		rpp = a[:mid + 1]
		low = mid + 1
	else:
		high = mid - 1
print(b.index(rpp))


try:
	n = int(input())
	a = input()
	b = input()
	low = 0
	high = n - 1
	res = float('inf')
	while low <= high:
		mid = (low + high) // 2
		if a[:mid + 1] in b:
			res = a[:mid + 1]
			low = mid + 1
		else:
			high = mid - 1
	print(b.index(res))
except:
	pass


n = int(input())
a = input()
b = input()
b *= 2
i = n // 2
j = i // 2
while j:
	if b.find(a[:i]) >= 0:
		i += j
	else:
		i -= j
	j //= 2
while b.find(a[:i]) < 0:
	i -= 1
print(b.find(a[:i]))


n = int(input())
a = input()
b = input()
b += b
pos = []
lens = []
i = j = 0
while j < len(b):
	if a[i] == b[j]:
		pos.append(j)
		l = 1
		i += 1
		j += 1
		while i < len(a) and j < len(b):
			if a[i] == b[j]:
				l += 1
				i += 1
				j += 1
				if j == len(b):
					lens.append(l)
			else:
				lens.append(l)
				i = 0
				break
	else:
		i = 0
		j += 1
m_idx = lens.index(max(lens))
print(pos[m_idx] % n)


t = int(input())
a = input()
b = input()
i = 0
res = -99999999
j = 0
flag = -1
while j < t:
	k = j
	while i < t and j < 2 * t and (a[i] == b[j % t]):
		i += 1
		j += 1
	if k - j != 0:
		prev = res
		res = max(res, j - k)
		if prev < res:
			flag = k
		i = 0
		continue
	j += 1
print(flag)


n = int(input())
a = input()
b = input()
low = 0
high = n - 1
res = float('inf')
while low <= high:
	mid = (low + high) // 2
	if a[:mid + 1] in b:
		res = a[:mid + 1]
		low = mid + 1
	else:
		high = mid - 1
ans = b.index(res)
print(ans)


def solve(sa, sb):
	m = len(sa)
	n = len(sb)
	i = j = 0
	curr_start = -1
	cur_len = 0
	largest_start = -1
	max_len = 0
	while i < m:
		if sa[i] == sb[j]:
			cur_len += 1
			if cur_len == 1:
				curr_start = j
			i += 1
			j = (j + 1) % n
		else:
			if cur_len > max_len:
				max_len = cur_len
				largest_start = curr_start
			cur_len = 0
			j = (j + (i == 0)) % n
			i = 0
			if largest_start != -1 and j == largest_start:
				break
	return largest_start

def main():
	_ = input()
	sa = input()
	sb = input()
	print(solve(sa, sb))
main()


try:
	n = int(input())
	a = input()
	b = input()
	b *= 2
	n0 = n // 2
	n1 = n0 // 2
	while n1:
		if b.find(a[:n0]) >= 0:
			n0 += n1
		else:
			n0 -= n1
		n1 //= 2
	while b.find(a[:n0]) < 0:
		n0 -= 1
	print(b.find(a[:n0]))
except:
	EOFError