Problem:


Score : 600 points

Problem Statement

Given are two sequences a=\{a_0,\ldots,a_{N-1}\} and b=\{b_0,\ldots,b_{N-1}\} of N non-negative integers each.

Snuke will choose an integer k such that 0 \leq k < N and an integer x not less than 0, to make a new sequence of length N, a'=\{a_0',\ldots,a_{N-1}'\}, as follows:

a_i'= a_{i+k \mod N}\ XOR \ x

Find all pairs (k,x) such that a' will be equal to b.

What is \mbox{ XOR }?

The XOR of integers A and B, A \mbox{ XOR } B, is defined as follows:

When A \mbox{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.

For example, 3 \mbox{ XOR } 5 = 6. (In base two: 011 \mbox{ XOR } 101 = 110.)

Constraints

1 \leq N \leq 2 \times 10^5

0 \leq a_i,b_i < 2^{30}

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_0 a_1 ... a_{N-1}
b_0 b_1 ... b_{N-1}

Output

Print all pairs (k, x) such that a' and b will be equal, using one line for each pair, in ascending order of k (ascending order of x for pairs with the same k).

If there are no such pairs, the output should be empty.

Sample Input 1

3
0 2 1
1 2 3

Sample Output 1

1 3

If (k,x)=(1,3),

a_0'=(a_1\ XOR \ 3)=1

a_1'=(a_2\ XOR \ 3)=2

a_2'=(a_0\ XOR \ 3)=3

and we have a' = b.

Sample Input 2

5
0 0 0 0 0
2 2 2 2 2

Sample Output 2

0 2
1 2
2 2
3 2
4 2

Sample Input 3

6
0 1 3 7 6 4
1 5 4 6 2 3

Sample Output 3

2 2
5 5

Sample Input 4

2
1 2
0 0

Sample Output 4

No pairs may satisfy the condition.



Sample input:
3
0 2 1
1 2 3


Sample output:
1 3

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def Z(S):
    n = len(S)
    res = [0] * n
    res[0] = n
    l = r = 0
    for i in range(1, n):
        if res[i - l] < r - i: # 過去の結果が全て使える
            res[i] = res[i - l]
        else:
            l = i
            r = max(i, r) # i < r ならば過去の結果が一部使える
            while r < n and S[r - l] == S[r]: r += 1
            res[i] = r - l
    return res

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    C = [A[i] ^ A[(i + 1) % n] for i in range(n)]
    D = [B[i] ^ B[(i + 1) % n] for i in range(n)]
    prefix = Z(C + D + D)
    res = []
    for k in range(n, 0, -1):
        if prefix[n + k] >= n:
            print(n - k, A[n - k] ^ B[0])
resolve()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF = 1 << 60
MOD = 10**9 + 7 # 998244353
input = lambda:sys.stdin.readline().rstrip()

def Z(S):
    n = len(S)
    res = [0] * n
    res[0] = n
    l = r = 0
    for i in range(1, n):
        if res[i - l] < r - i: # 過去の結果が全て使える
            res[i] = res[i - l]
        else:
            l = i
            r = max(i, r) # i < r ならば過去の結果が一部使える
            while r < n and S[r - l] == S[r]: r += 1
            res[i] = r - l
    return res

def resolve():
    n = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))

    C = [A[i] ^ A[(i + 1) % n] for i in range(n)]
    D = [B[i] ^ B[(i + 1) % n] for i in range(n)]
    prefix = Z(C + D + D)
    res = []
    for k in range(n):
        if prefix[n + k] >= n:
            res.append(((n - k) % n, A[0] ^ B[k]))
    res.sort()
    for pair in res:
        print(*pair)
resolve()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    x = [0] * N
    for i in range(L):
        for k in range(N):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if x[k] is None:
                continue
            if l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x[k] += 1 << i
            elif l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            else:
                x[k] = None

    ans = []
    for k, xx in enumerate(x):
        if xx is not None:
            ans.append('%d %d' % (k, xx))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# import time
import sys
from collections import Counter, defaultdict
buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline


def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))

gpw = None


class RH():
    def __init__(self, s, base, mod):
        self.base = base
        self.mod = mod

        l = len(s)
        self.h = h = [0]*(l+1)
        tmp = 0
        for i in range(l):
            tmp = (tmp*base + s[i]) % mod
            h[i+1] = tmp

        global gpw
        if gpw is None:
            self.pw = pw = [1]*(len(s)+1)
            v = 1
            for i in range(l):
                pw[i+1] = v = v * base % mod
            gpw = pw
        else:
            self.pw = gpw

    def calc(self, l, r):
        return (self.h[r] - self.h[l] * self.pw[r-l]) % self.mod


def slv(N, A, B):
    L = max(max(A), max(B)).bit_length()
    ah = []
    bh = []
    bnh = []
    for i in range(L):
        ta = []
        tb = []
        tbn = []
        for a, b in zip(A, B):
            ta.append(a >> i & 1)
            tb.append(b >> i & 1)
            tbn.append(tb[-1] ^ 1)
        ah.append(RH(ta, 641, 10**9+7))
        bh.append(RH(tb, 641, 10**9+7))
        bnh.append(RH(tbn, 641, 10**9+7))

    ans = []
    x = [0] * N
    for i in range(L):
        for k in range(N):
            l = ah[i].calc(k, N)
            r = ah[i].calc(0, k)
            if x[k] is None:
                continue
            if l == bnh[i].calc(0, N-k) and r == bnh[i].calc(N-k, N):
                x[k] += 1 << i
            elif l == bh[i].calc(0, N-k) and r == bh[i].calc(N-k, N):
                pass
            else:
                x[k] = None
    for k, xx in enumerate(x):
        if xx is not None:
            ans.append('%d %d' % (k, xx))

    return ans


def main():
    N = read_int()
    A = read_int_n()
    B = read_int_n()
    print(*slv(N, A, B), sep='\n')

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class MP:
    def __init__(self,p):
        # Preprocess: Longest border
        self.pattern = p
        n = len(p)
        A = [-1]*(n+1)
        j = -1
        for i in range(n):
            while j >= 0 and p[j] != p[i]:
                j = A[j]
            j += 1
            A[i+1] = j
        self.border = A

    def findall(self, t):
        p = self.pattern
        A = self.border
        res = list()
        j = 0
        for i in range(len(t)):
            while j >= 0 and p[j] != t[i]:
                j = A[j]
            j += 1
            if j == len(p):
                res.append(i-j+1)
                j = A[j]
        return res

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

m = MP(bxor)
kls = m.findall(axor + axor[:-1])

for k in kls:
    x = b[0] ^ a[k]
    print(k,x)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
txt = axor + axor
pattern = bxor
ans = list()
j = 0
for i in range(2*n-1):
    while j >= 0 and pattern[j] != txt[i]:
        j = mp[j]
    j += 1
    if j == n:
        k = i-j+1
        x = b[0] ^ a[k]
        ans.append([k,x])
        j = mp[j]


for k,x in ans:
    print(k,x)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

axor=[0]*n
bxor=[0]*n

for i in range(n-1):
    axor[i] = a[i] ^ a[i+1]
    bxor[i] = b[i] ^ b[i+1]

axor[-1] = a[0] ^ a[-1]
bxor[-1] = b[0] ^ b[-1]

def MP(it):
    n = len(it)
    res = [0]*(n+1)
    res[0] = -1
    j = -1
    for i in range(n):
        while j >= 0 and it[i] != it[j]:
            j = res[j]
        j += 1
        res[i+1] = j
    return res

mp = MP(bxor)
shift = [1]*(n+1)
for i in range(n):
    shift[i+1] = i+1 - mp[i+1]
txt = axor + axor
head = 0
ans = list()
start = 0
while head < n:
    for i in range(start,n):
        if bxor[i] != txt[head+i]:     
            start = max(0,i - shift[i])
            head += shift[i]
            break
    else:
        x = b[0] ^ a[head]
        ans.append([head, x])
        start = i+1 - shift[i+1]
        head += shift[i+1]


for k,x in ans:
    print(k,x)

Submission status: Accepted

Solution code:
#Z[i]:length of the longest list starting from S[i] which is also a prefix of S
#O(|S|)
def Z_algorithm(s):
    N = len(s)
    Z_alg = [0]*N

    Z_alg[0] = N
    i = 1
    j = 0
    while i < N:
        while i+j < N and s[j] == s[i+j]:
            j += 1
        Z_alg[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i+k < N and k + Z_alg[k]<j:
            Z_alg[i+k] = Z_alg[k]
            k += 1
        i += k
        j -= k
    return Z_alg

N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=[a[i]^a[i-1] for i in range(0,N)]
B=[b[i]^b[i-1] for i in range(0,N)]

data=B+['?']+A+A
s=Z_algorithm(data)
for i in range(N+1,2*N+1):
    if s[i]>=N:
        print(i-N-1,a[i-N-1]^b[0])

Submission status: Accepted

Solution code:
def divisors(M):#Mの約数列 O(n^(0.5+e))
    import math
    d=[]
    i=1
    while math.sqrt(M)>=i:
        if M%i==0:
            d.append(i)
            if i**2!=M:
                d.append(M//i)
        i=i+1
    d.sort()
    return d

import numpy as np
N=int(input())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
A=np.array([a[i]^a[i-1] for i in range(0,N)])
B=np.array([b[i]^b[i-1] for i in range(0,N)])
d=divisors(N)
perioda=N
for i in range(0,len(d)):
    test=np.roll(A,-d[i])
    if all(test==A):
        perioda=min(perioda,d[i])

periodb=N
for i in range(0,len(d)):
    test=np.roll(B,-d[i])
    if all(test==B):
        periodb=min(periodb,d[i])

if perioda==periodb:
    A=A[:perioda]
    B=B[:periodb]
    kouho=[]
    for i in range(0,len(B)):
        if A[i]==B[0]:
            kouho.append(i)
    ans=-1
    for i in range(0,len(kouho)):
        test=np.roll(A,-kouho[i])
        if all(test==B):
            ans=kouho[i]
            break
    if ans!=-1:
        for i in range(0,N//perioda):
            print(ans+perioda*i,a[ans+perioda*i]^b[0])

Submission status: Accepted

Solution code:
def z_algo(s):
    """文字列sについて、各iについて「SとS[i:|S|]の最長共通接頭辞の長さ」
    を記録した配列をO(|S|)で構築する
    """
    res = [0] * len(s)
    res[0] = len(s)
    i, j = 1, 0
    while i < len(s):
        while i + j < len(s) and s[j] == s[i + j]:
            j += 1
        res[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + res[k] < j:
            res[i + k] = res[k]
            k += 1
        i, j = i + k, j - k
    return res


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

diff_a = []
diff_b = []
for i in range(n):
    diff_a.append(a[(i + 1) % n] ^ a[i % n])
    diff_b.append(b[(i + 1) % n] ^ b[i % n])

diff_a2b = diff_b + diff_a + diff_a
t = z_algo(diff_a2b)

for i in range(n, 2 * n):
    if t[i] >= n:
        print(i - n, a[i - n] ^ b[0] )

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
from pprint import pprint
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint


sys.setrecursionlimit(2147483647)
INF = 10 ** 15
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


def z_algorithm(S):
    l = len(S)
    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

n = I()
A = LI()
B = LI()
ax = [A[i%n] ^ A[(i+1)%n] for i in range(2 * n)]
bx = [B[i%n] ^ B[(i+1)%n] for i in range(n)]
z_box = z_algorithm(bx + ax)
for j in range(n, 2 * n):
    if z_box[j] >= n:
        print(j - n, B[0] ^ A[j - n])

Submission status: Accepted

Solution code:
# coding: utf-8

def main():

	# N = 0
	# a = []
	# b = []
	# with open("C:/Users/admin/Downloads/random_05") as f:
	# 	N = int(f.readline())
	# 	a = [int(x) for x in f.readline().split()]
	# 	b = [int(x) for x in f.readline().split()]

	N = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]

	xor_a = [a[i] ^ a[(i+1) % N] for i in range(len(a))]
	xor_b = [b[i] ^ b[(i+1) % N] for i in range(len(b))]

	kmp = KmpSearch(xor_a + xor_a, xor_b)

	ans = kmp.full_search()
	for k in ans:
		if k == len(a):
			break
		print(str(k) + " " + str(a[0 + k] ^ b[0]))

class KmpSearch:
	def __init__(self, target, pattern):
		self.target = target
		self.pattern = pattern
		self.__table = self.__create_kmp_table()

	def full_search(self):
		if len(self.pattern) > len(self.target):
			return -1

		res = []
		i = 0
		p = 0
		while i < len(self.target):
			if self.pattern[p] == self.target[i]:
				i += 1
				p += 1

				if p == len(self.pattern):
					res.append(i-p)
					i -= 1
					p = self.__table[p-1]
			elif p == 0:
				i += 1
			else:
				p = self.__table[p]

		return res

	def __create_kmp_table(self):
		table = [0 for x in range(len(self.pattern))]

		j = 0
		for i in range(1, len(self.pattern)):
			table[i] = j
			if self.pattern[j] == self.pattern[i]:
				j += 1
			else:
				j = 0

		return table

if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
f = [0]*n
g = [0]*n
for i in range(n):
  f[i] = a[i] ^ a[(i+1)%n]
  g[i] = b[i] ^ b[(i+1)%n]

def KMP(S, W):
    ls, lw = len(S), len(W)
    m, i = 0, 0
    T = _KMP_table(W)
    res = list()
    while m + i < ls:
        if W[i] == S[m + i]:
            i += 1
            if i == lw:
                res.append(m)
                m += i - T[i]
                if i > 0:
                    i = T[i]
        else:
            m += i - T[i]
            if i > 0:
                i = T[i]
    return res


def _KMP_table(W):
    W += ['$']
    lw = len(W)
    T = [0] * lw
    T[0] = -1
    i, j = 2, 0
    while i < lw:
        if W[i - 1] == W[j]:
            T[i] = j + 1
            i += 1
            j += 1
        elif j > 0:
            j = T[j]
        else:
            T[i] = 0
            i += 1
    return T
res = KMP(f*2, g)
for x in res:
  if x < n:
    print(x, a[x]^b[0])

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = a + a[:-1]

da = [a[i] ^ a[i+1] for i in range(len(a) - 1)]
db = [b[i] ^ b[i+1] for i in range(len(b) - 1)]


fail = [0 for i in range(len(da))]
fail[0] = -1
p = 0
for q in range(2, len(da)):
    while p >= 0 and da[q-1] != da[p]:
        p = fail[p]
    p += 1
    fail[q] = p

p = 0
q = 0
while p + q < len(da):
    if db[q] == da[p+q]:
        if q == len(db) - 1:
            print(p, a[p] ^ b[0])
            p += q - fail[q]
            q = fail[q]
        else:
            q += 1
    else:
        p += q - fail[q]
        if q > 0:
            q = fail[q]

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            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 += 1
                z[i] = j
                c = i
        return z
    n = I()
    a = LI()
    b = LI()
    c = [a[i]^a[(i+1)%n] for i in range(n)]
    d = [b[i]^b[(i+1)%n] for i in range(n)]
    z = Z_algorithm(d+c*2)[n:]
    for k in range(n):
        if z[k] >= n:
            print(k,a[k]^b[0])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
####################################### Define
maxN = int(6e5 + 100)
a = [0] * maxN
b = [0] * maxN
ans = [0] * maxN
####################################### Functions
def solve() :
    L = R = 0
    for i in range(2, 3 * n + 1) :
        if i > R :
            L = R = i
            while R + 1 <= 3 * n and (a[i] ^ a[1]) == (a[R + 1] ^ a[R - L + 2]): R += 1
#            print(a[i] ^ a[1], a[R + 1] ^ b[R - L + 2], R, L, "\n")
            ans[i] = R - L + 1
        else :
            k = i - L + 1
            if ans[k] < R - i + 1 : ans[i] = ans[k]
            else :
                L = i
                while R + 1 <= 3 * n and (a[i] ^ a[1]) == (a[R + 1] ^ a[R - L + 2]): R += 1
                ans[i] = R - L + 1
####################################### Main
n = int(input())
inp = input().split()
for i in range(n + 1, 2 * n + 1) : a[i] = int(inp[i - n - 1])
for i in range(2 * n + 1, 3 * n + 1) : a[i] = a[i - n]
inp = input().split()
for i in range(1, n + 1) : a[i] = int(inp[i - 1])

solve()

for i in range(n + 1, 2 * n + 1):
    if ans[i] >= n:
        print(i - n - 1, (a[i] ^ a[1]))

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def Z_algorithm(s):
        n = len(s)
        z = [0]*n
        z[0] = n
        c = 1
        for i in range(1,n):
            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 += 1
                z[i] = j
                c = i
        return z
    n = I()
    a = LI()
    b = LI()
    c = [a[i]^a[(i+1)%n] for i in range(n)]
    d = [b[i]^b[(i+1)%n] for i in range(n)]
    z = Z_algorithm(d+c*2)[n:2*n]
    for k in range(n):
        if z[k] >= n:
            print(k,a[k]^b[0])
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
import sys
from itertools import combinations, permutations, product, combinations_with_replacement, accumulate
from heapq import heapify, heappop, heappush, heappushpop
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict, deque
from math import sqrt, log, floor, ceil, factorial, cos, sin, pi#, gcd
from fractions import gcd
from operator import mul
from functools import reduce
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
LINF = 2**63-1
NIL = -LINF
MOD = 10**9+7
MGN = 4
def AST(exp: bool, msg: str = ""): assert exp, msg
def TAST(exp: bool, msg = ""):
    if exp is False: print("TAssertionError:", msg)
    while exp is False:
        pass
def II(): return int(input())
def IF(): return float(input())
def IS(): return input().replace('\n', '')
def ILCI(n: int): return [II() for _ in range(n)]
def ILCF(n: int): return [IF() for _ in range(n)]
def ILI(): return list(map(int, input().split()))
def ILLI(n: int): return [[int(j) for j in input().split()] for i in range(n)]
def ILF(): return list(map(float, input().split()))
def ILLF(n: int): return [[float(j) for j in input().split()] for i in range(n)]
def LTOS(lst: list, sep: str = ' '): return sep.join(map(str, lst))
def DEC(lst: list): return list(map(lambda x: x-1, lst))
def INC(lst: list): return list(map(lambda x: x+1, lst))

def z_algo(S: str) -> list:
    N = len(S)
    if N == 0:
        return []
    ln = [0] * N
    ln[0] = N  
    i = 1
    w = 0
    while i < N:
        while i + w < N and S[w] == S[i + w]:
            w += 1
        ln[i] = w  
        if w == 0:
            i += 1
        else:
            j = 1
            while i + j < N and j + ln[j] < w:
                ln[i+j] = ln[j]
                j += 1
            i += j
            w -= j
    return ln

def z_algo_search(S: str, W: str) -> list:
    lens = z_algo(W+S)
    if len(lens) == 0:
        return []
    SL = len(S)
    WL = len(W)
    slens = lens[WL:]
    res = []
    for i in range(SL):
        if slens[i] >= WL:
            res.append(i)
    return res

def xor_next(A: list) -> list:    
    N = len(A)
    res = []
    for i in range(N-1):
        res.append(A[i]^A[i+1])
    
    res.append(A[-1]^A[0])
    return res

def main():
    N = II()
    A = ILI()
    B = ILI()

    C = xor_next(A)
    D = xor_next(B)

    # C の中から D を周期的にを探す
    pos = z_algo_search(C*2, D)
    pos = list(filter(lambda x: x < N, pos))
    
    ans = []
    for i in pos:
        ans.append((i, A[i] ^ B[0]))

    for e in ans:
        print(e[0], e[1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from fractions import gcd
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9 +7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
a = inputIL()
b = inputIL()

difa = [0]*N
difb = [0]*N
for i in range(N-1):
  difa[i] = a[i]^a[i+1]
  difb[i] = b[i]^b[i+1]
difa[N-1] = a[0]^a[N-1]
difb[N-1] = b[0]^b[N-1]

if set(difa) != set(difb):
  exit()

memo = []
for i in range(N):
  j = 0
  while difa[(i+j)%N] == difb[j%N]:
    j += 1
    if j == N:
      print(i,a[i]^b[0])
      memo.append(i)
      break
  if len(memo) == 2:
    break

if len(memo) == 2:
  d = memo[1]-memo[0]
  k = memo[1]+d
  while k < N:
    print(k,a[k]^b[0])
    k += d

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

class KmpSearch:
  def __init__(self, word):
    self.word = word
    self.table = [0] * (len(word) + 1)
    self.table[0] = -1
    i, j = 0, 1
    while j < len(self.word):
      matched = self.word[i] == self.word[j]
      if not matched and i > 0:
        i = self.table[i]
      else:
        if matched:
          i += 1
        j += 1
        self.table[j] = i
  def search(self, text):
    table = self.table
    word = self.word
    i, p = 0, 0
    res = []
    while i < len(text):
      if text[i] == word[p]:
        i += 1
        p += 1
      elif p == 0:
        i += 1
      else:
        p = table[p]
      if p == len(word):
        res.append(i - p)
        p = table[p]
    return res

xa = [0] * N
xb = [0] * N
for i in range(N):
  xa[i] = a[i - 1] ^ a[i]
  xb[i] = b[i - 1] ^ b[i]

kmp = KmpSearch(xa)
res = kmp.search(xb + xb[: -1])
rres = []
for x in res: rres.append(((N - x) % N, a[0] ^ b[x]))
rres.sort(key = lambda x: (x[0], x[1]))
for r in rres: print(*r)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ta = [[0] * N for _ in range(30)]
tb = [[0] * N for _ in range(30)]
mxl = max(max(a), max(b)).bit_length()
for i in range(mxl):
  x = 1 << i
  for j in range(N):
    ta[i][j] = int((a[j] & x) > 0)
    tb[i][j] = int((b[j] & x) > 0)

class KmpSearch:
  def __init__(self, word):
    self.word = word
    self.table = [0] * (len(word) + 1)
    self.table[0] = -1
    i, j = 0, 1
    while j < len(self.word):
      matched = self.word[i] == self.word[j]
      if not matched and i > 0:
        i = self.table[i]
      else:
        if matched:
          i += 1
        j += 1
        self.table[j] = i
  def search(self, text):
    table = self.table
    word = self.word
    i, p = 0, 0
    res = []
    while i < len(text):
      if text[i] == word[p]:
        i += 1
        p += 1
      elif p == 0:
        i += 1
      else:
        p = table[p]
      if p == len(word):
        res.append(i - p)
        p = table[p]
    return res
res = [0] * N
vis = [1 for _ in range(N)]
for i in range(mxl):
  kmp = KmpSearch(ta[i])
  s = [0] * (2 * N - 1)
  for j in range(2 * N - 1): s[j] = tb[i][j % N] ^ 1
  xs = set(kmp.search(s))
  tvis = [0] * N
  for j in range(N):
    tvis[j] |= (j in xs)
    res[j] += (j in xs) << i
  xs = set(kmp.search(tb[i] + tb[i][: -1]))
  for j in range(N):
    tvis[j] |= (j in xs)
  for j in range(N):
    vis[j] &= tvis[j]
#print(res, vis)
rres = []
for i in range(N):
  if vis[i]: rres.append(((N - i) % N, res[i]))
rres.sort(key = lambda x: (x[0], x[1]))
for r in rres: print(*r)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))


C = [0] * (2 * N - 1)
D = [0] * N
for i in range(2 * N - 1):
    C[i] = A[i % N] ^ A[(i + 1) % N]
    D[i % N] = B[i % N] ^ B[(i + 1) % N]

class KMP:

    def __init__(self, W):
        self.W = W
        self.L = len(W)
        self.T = self._build(W)

    def _build(self, W):
        T = [0] * self.L
        T[0] = -1
        T[1] = 0
        i = 2
        j = 0

        while i < self.L:
            if W[i - 1] == W[j]:
                T[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = T[j]
            else:
                T[i] = 0
                i += 1

        return T

    def search(self, S):
        m = 0
        i = 0
        L = len(S)
        while m + i < L:
            # print(m, i)
            if self.W[i] == S[m + i]:
                i += 1
                if i == self.L:
                    i -= 1
                    ret = m
                    m = m + i - self.T[i]
                    i = self.T[i]
                    yield ret
            else:
                m = m + i - self.T[i]
                if i > 0:
                    i = self.T[i]

# def ok(x, i):
#     for j in range(N):
#         if A[(j + i) % N] ^ B[j] != x:
#             return False
#     return True
#
#
# for i in range(N):
#     x = A[i] ^ B[0]
#     if ok(x, i):
#         print(i, x)

kmp = KMP(D)
for x in kmp.search(C):
    xor = A[x] ^ B[0]
    print(x, xor)