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:
from collections import defaultdict
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = []
B = []
ans = []
for i in range(N):
    A.append(a[i]^a[(i+1)%N])
    B.append(b[i]^b[(i+1)%N])
if A == B == [A[0]]*N:
    for i in range(N): 
        ans.append((i,a[i]^b[0]))
else:
    A += A    
    d = defaultdict(list)
    for i in range(N):
        d[B[i]].append(i)
    i = 0
    ans = []
    while i < N:
        ok = True
        for j in range(N):
            if B[N-j-1] != A[N-j-1+i]:
                if d[A[N-j-1]] == []:
                    i += N
                    ok = False
                    break
                else:
                    i += N - d[A[N-j-1+i]][-1] - 1
                    ok = False
                    break
        if ok:
            ans.append((i,a[i]^b[0]))
            if len(d[A[N-1+i]]) == 1:
                i += N
            else:
                i += N - d[A[N-1+i]][-2] - 1
for x in ans:
    print(*x)

Submission status: Accepted

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

# process/output
# A[i+k+]^A[i+k+1]=B[i]^B[i+1]となるkを求め,kからxを求める
AX = [A[i]^A[i-1] for i in range(N)]
AX += AX
BX = [B[i]^B[i-1] for i in range(N)]

#print(AX)
#print(BX)

# BXの頭と終わりが同じ数字の並びの場合、その数mを求める
m = 0
for i in range(1, N):
    if BX[m] == BX[i]:
        m += 1
    else:
        m = 0
#print(m)

i, j, k = 0, 0, 0
while k < N:
    while True:
        #print("i,j: {},{},{}".format(i,j,k))
        if AX[i] == BX[j]:
            if j == N-1:
                print(k, A[k]^B[0])
                i += 1
                j = m
                break
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:
            i += 1
            break
    
    k = i-j

Submission status: Accepted

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

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX[:-1]

# KMP法

LEN=len(BX)
MP=[-1]*(LEN+1) #「接頭辞と接尾辞が最大何文字一致しているか」を記録する配列
BX+="0" # 最後に入らない文字をつけ加える

NOW=-1 # 何文字一致しているか.

for i in range(LEN):
    while NOW>=0 and BX[i]!=BX[NOW]: # 一致していなかったら0から数え直すのではなく, MP[NOW]から数える.
        NOW=MP[NOW]
    NOW+=1
    
    if BX[i+1]==BX[NOW]: # ここだけMPと違う
        MP[i+1]=MP[NOW]
    else:
        MP[i+1]=NOW
        
LEN2=len(AX)
AX+="0" # 最後に入らない文字をつけ加える

MP_SEARCH=[0]*(LEN2+1) # その文字までで何個一致しているかを調べる. LEN文字一致したらSが検出できたということ.
NOW=0
for i in range(LEN2):
    while NOW>=0 and AX[i]!=BX[NOW]:
        NOW=MP[NOW]
    NOW+=1

    if AX[i+1]==BX[NOW]: # ここだけMPと違う
        MP_SEARCH[i+1]=MP_SEARCH[NOW]
    else:
        MP_SEARCH[i+1]=NOW
        
    MP_SEARCH[i]=NOW

    if NOW==LEN: # LEN文字一致したら, MP[LEN]から数える.
        NOW=MP[NOW]
        
for i in range(LEN2):
    if MP_SEARCH[i]==LEN:
        print(i-LEN+1,A[i-LEN+1]^B[0])

Submission status: Accepted

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

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX[:-1]

# MP法


LEN=len(BX)
MP=[-1]*(LEN+1) #「接頭辞と接尾辞が最大何文字一致しているか」を記録する配列
NOW=-1 # 何文字一致しているか.

for i in range(LEN):
    while NOW>=0 and BX[i]!=BX[NOW]: # 一致していなかったら0から数え直すのではなく, MP[NOW]から数える.
        NOW=MP[NOW]
    NOW+=1
    MP[i+1]=NOW

LEN2=len(AX)

MP_SEARCH=[0]*(LEN2) # その文字までで何個一致しているかを調べる. LEN文字一致したらSが検出できたということ.
NOW=0
for i in range(LEN2):
    while NOW>=0 and AX[i]!=BX[NOW]:
        NOW=MP[NOW]
    NOW+=1
    MP_SEARCH[i]=NOW

    if NOW==LEN: # LEN文字一致したら, MP[LEN]から数える.
        NOW=MP[NOW]
        
for i in range(LEN2):
    if MP_SEARCH[i]==LEN:
        print(i-LEN+1,A[i-LEN+1]^B[0])

Submission status: Accepted

Solution code:
def get_next_int():
    return int(input().rstrip("\n"))


def get_next_ints(delim=" "):
    return tuple([int(x) for x in input().rstrip("\n").split(delim)])


def main():
    n = get_next_int()

    a = get_next_ints()
    b = get_next_ints()

    a_offsets = []
    b_offsets = []
    for i in range(n):
        a_offsets.append(str(a[i] ^ a[i - 1]))
        b_offsets.append(str(b[i] ^ b[i - 1]))
    #print(a_offsets)
    #print(b_offsets)
    a_text = " ".join(a_offsets)
    b_text = " ".join(b_offsets)
    target_text = a_text + " " + a_text
    start_pos = 0
    if target_text.find(b_text, start_pos) >= 0:
        fisrt_pos = target_text.find(b_text, start_pos)
        fisrt_pos_diff = target_text[:fisrt_pos].count(" ")
        fisrt_xor_diff = b[0] ^ a[fisrt_pos_diff]
        print(fisrt_pos_diff, fisrt_xor_diff)
        if target_text.find(b_text, fisrt_pos+1) >= 0:
            second_pos = target_text.find(b_text, fisrt_pos+1)
            second_pos_diff = target_text[:second_pos].count(" ")
            if second_pos_diff < len(a):
                second_xor_diff = b[0] ^ a[second_pos_diff]
                print(second_pos_diff, second_xor_diff)
                interval = (second_pos_diff - fisrt_pos_diff)
                remain = (n - second_pos_diff - 1) // (second_pos_diff - fisrt_pos_diff)
                for i in range(remain):
                    print(second_pos_diff + interval * (i + 1), [fisrt_xor_diff,second_xor_diff ][i % 2])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353


class KMP:
    def __init__(self, needle):
        """
        https://ja.wikipedia.org/wiki/クヌース–モリス–プラット法
        :param typing.Sequence needle: 何を検索するか
        """
        self._needle = needle
        kmp = [0] * (len(needle) + 2)
        kmp[0] = -1
        kmp[1] = 0
        i = 2
        j = 0
        while i < len(needle):
            if needle[i - 1] == needle[j]:
                kmp[i] = j + 1
                i += 1
                j += 1
            elif j > 0:
                j = kmp[j]
            else:
                kmp[i] = 0
                i += 1
        self._kmp = kmp

    def index_of(self, haystack, m=0, i=0):
        """
        m + (haystack[m:] の何番目に needle があるか)
        見つからなければ -1
        needle[i:] のみ比較する
        :param typing.Sequence haystack: 何から検索するか
        :param int m: The position of the current character in haystack
        :param int i: The position of the current character in needle
        :rtype: int
        """
        while m + i < len(haystack):
            if self._needle[i] == haystack[m + i]:
                i += 1
                if i == len(self._needle):
                    return m
            else:
                m += i - self._kmp[i]
                if i > 0:
                    i = self._kmp[i]
        return -1

    def search(self, haystack):
        """
        ret[i]: haystack[i:i+len(needle)] == needle
        :param typing.Sequence haystack: 何から検索するか
        :rtype: list of bool
        """
        ret = [False] * len(haystack)
        m = 0
        i = 0
        while m + i < len(haystack):
            m = self.index_of(haystack, m=m, i=i)
            if m < 0:
                break
            ret[m] = True
            m += len(self._needle) - self._kmp[len(self._needle) - 1] - 1
            i = max(0, self._kmp[len(self._needle) - 1])
        return ret


N = int(sys.stdin.buffer.readline())
A = list(map(int, sys.stdin.buffer.readline().split()))
B = list(map(int, sys.stdin.buffer.readline().split()))


def test():
    ans = []
    # k が決まれば x も決まる
    for k in range(N):
        b = np.roll(B, k)
        x = A[0] ^ b[0]
        a = A ^ x
        if np.all(a == b):
            ans.append((k, x))
    for r in ans:
        print(*r)


# 解説
# 隣合う値同士の XOR が全て等しければ OK
xa = []
xb = []
for a1, a2 in zip(A, A[1:] + [A[0]]):
    xa.append(a1 ^ a2)
for b1, b2 in zip(B, B[1:] + [B[0]]):
    xb.append(b1 ^ b2)

kmp = KMP(xb)
k_ok = kmp.search(xa + xa)
for k in range(N):
    if k_ok[k]:
        x = A[k] ^ B[0]
        print(k, x)

Submission status: Accepted

Solution code:
# F - Xor Shift

from itertools import chain

N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
assert len(a) == N and len(b) == N

# 直前の要素とのxor (循環)
a_xor = [a[i] ^ a[(i + 1) % N] for i in range(N)]
# 直前の要素とのxor (先頭を除く)
b_xor = [b[i] ^ b[i + 1] for i in range(N - 1)]

# (k,x)が解 ⇔ a_xor[k:]がb_xorと一致, x = b[0] XOR a[k]

def kmp_search(T, P):
    m = len(P)
    matches = []
    pi = compute_prefix_func(P)
    q = 0  # number of characters matched
    for i, t in enumerate(T):
        while q > 0 and P[q] != t:
            q = pi[q]  # next character does not match
        if P[q] == t:
            q += 1     # next character matches
        if q == m:
            matches.append(i - (m - 1))
            q = pi[q]  # look for the next match
    return matches

def compute_prefix_func(P):
    m = len(P)
    pi = [0] * (m + 1)
    k = 0
    for q in range(1, m):
        while k > 0 and P[k] != P[q]:
            k = pi[k]
        if P[k] == P[q]:
            k += 1
        pi[q + 1] = k
    return pi

    # pi : {1,2,...,m} -> {0,1,...,m-1}
    # pi[q] = max {k : k < q and P[:q].endswith(P[:k])}

for k in kmp_search(chain(a_xor, a_xor), b_xor):
    if k < N:
        x = b[0] ^ a[k]
        print(k, x)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

class RollingHash() :
    # mod ex. (1<<61)-1, (1<<31)-1
    # 文字列のときはxをordに通すのを忘れない！！
    def __init__(self, x, base=26, mod=(1<<61)-1) :
        self.hash = [0]
        self.pow = [1]
        self.mod = mod
        
        for xi in x :
            self.hash.append((self.hash[-1] * base + xi) % mod)
            self.pow.append(self.pow[-1] * base % mod)
            
    # [l, r)
    def get(self, l, r) :
        return (self.hash[r] - self.hash[l] * self.pow[r-l]) % self.mod

da = [a[i] ^ a[(i + 1) % N] for i in range(N)] * 2
db = [b[i] ^ b[(i + 1) % N] for i in range(N)] * 2

RHa1 = RollingHash(da, base=1<<30)
RHa2 = RollingHash(da, base=1<<30, mod=(1<<31)-1)
RHb1 = RollingHash(db, base=1<<30)
RHb2 = RollingHash(db, base=1<<30, mod=(1<<31)-1)

hashb1 = RHb1.get(0, N)
hashb2 = RHb2.get(0, N)

for i in range(N) :
  if RHa1.get(i, N + i) == hashb1 and RHa2.get(i, N + i) == hashb2 :
    print(i, a[i] ^ b[0])

Submission status: Accepted

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

A.append(A[0])
B.append(B[0])

AX=[]
BX=[]
for i in range(N):
    AX.append(A[i]^A[i+1])
    BX.append(B[i]^B[i+1])

AX+=AX+[AX[0]]

# Rolling Hashで。

p=1<<30
mod=(1<<62)+1 # Hashがぶつからない, pと互いに素な数を適当に指定

A_TABLE=[0] # Rolling Hashのテーブル. 最初は0
B_TABLE=[0] # Rolling Hashのテーブル. 最初は0

for i in range(len(AX)):
    A_TABLE.append((p*A_TABLE[-1]%mod+AX[i])%mod) # テーブルを埋める

for i in range(len(BX)):
    B_TABLE.append((p*B_TABLE[-1]%mod+BX[i])%mod) # テーブルを埋める

def hash(i,j): # [i,j)のハッシュ値を求める
    return (A_TABLE[j]-A_TABLE[i]*pow(p,j-i,mod))%mod

BH=B_TABLE[-1]
ANS=[]
for i in range(N):
    if hash(i,i+N)==BH:
        ANS.append((i,A[i]^B[0]))

for a in ANS:
    print(*a)

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        for i in range(self.n):
            self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


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

a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]

a_xor_rh = RollingHash(a_xor)
b_xor_rh = RollingHash(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Accepted

Solution code:
class RollingHash:
    def __init__(self, s: list, base: int = 1007, mod: int = 10**9 + 7):
        self.s = s
        self.n = len(s)
        self.base = base
        self.mod = mod

        # preprocess
        self.h_cum = [0] * (self.n + 1)  # h_cum[i] = (hash of s[:i])
        self.b_pow = [1] * (self.n + 1)  # b_pow[i] = base ** i
        # for i in range(self.n):
        #     self.h_cum[i + 1] = (self.h_cum[i] * base + s[i]) % mod
        #     self.b_pow[i + 1] = (self.b_pow[i] * base) % mod
        for i, si in enumerate(s):
            self.h_cum[i + 1] = (self.h_cum[i] * base + si % mod) % mod
            self.b_pow[i + 1] = (self.b_pow[i] * base) % mod

    def get_hash(self, l: int, r: int) -> int:
        # get hash value of the substring s[l:r]
        hash_val = self.h_cum[r] - self.h_cum[l] * self.b_pow[r - l] % self.mod
        if hash_val < 0:
            hash_val += self.mod
        return hash_val


# class RollingHashMulti:
#     def __init__(self,
#                  s: list,
#                  base_list: list = [1007, 2009],
#                  mod_list: list = [10**9 + 7, 10**9 + 9]):
#         self.n = len(base_list)
#         self.base_list = base_list
#         self.mod_list = mod_list
#         self.rh_list = [
#             RollingHash(s, base_list[i], mod_list[i]) for i in range(self.n)
#         ]
#
#     def get_hash(self, l: int, r: int) -> tuple:
#         return tuple(self.rh_list[i].get_hash(l, r) for i in range(self.n))

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

# a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n * 2)]
# b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n * 2)]
a_xor = [a[i % n] ^ a[(i + 1) % n] for i in range(n)] * 2
b_xor = [b[i % n] ^ b[(i + 1) % n] for i in range(n)] * 2

a_xor_rh = RollingHash(a_xor)
b_xor_rh = RollingHash(b_xor)

b_hash = b_xor_rh.get_hash(0, n)
for k in range(n):
    if a_xor_rh.get_hash(k, k + n) == b_hash:
        x = a[k] ^ b[0]
        print(k, x)

Submission status: Accepted

Solution code:
num = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = []
d = []

for i in range(num):
    c.append(a[i] ^ a[(i+1)%num])
    d.append(b[i] ^ b[(i+1)%num])
    
c += c

# print(c)
# print(d)

# テーブル作成
table = [0]
k = 0
for i in range(1, num+1):
    table.append(k)
    if i == num:
        continue
    
    if d[i] == d[k]:
        k += 1
    else:
        k = 0

# print(table)

i = 0 # 探索される文字列の位置
j = 0 # 探索する文字列の位置
k = 0 # kの初期値
while k < num:
    
    while True:
        # print(i, j, k)
        if c[i] == d[j]:
            if j == num - 1:
                print(k, a[k] ^ b[0])
                i += 1
                j = table[num]
                k = i - j
                break
            
            i += 1
            j += 1
        elif j != 0:
            j -= 1
        else:    
            i += 1
            j = table[j]
            break
    
    k = i - j

Submission status: Accepted

Solution code:
def xor_next(values):
    result = [0] * len(values)
    for i in range(len(values)):
        result[i] = values[i] ^ values[(i+1) % len(values)]
    return result


def make_mp_table(values):
    result = [-1] * (len(values) + 1)
    j = -1
    for i in range(len(values)):
        while j != -1 and values[j] != values[i]:
            j = result[j]
        j += 1
        result[i+1] = j
    return result


def mp_find(target, pattern, table):
    result = []
    j = 0
    for i in range(len(target)):
        while(j != -1 and pattern[j] != target[i]):
            j = table[j]
        j += 1
        if j == len(pattern):
            result.append(i-(j-1))
            j = table[j]
    return result


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

    xa = xor_next(a)
    xb = xor_next(b)
    mp_t = make_mp_table(xa)
    xb += xb
    res = mp_find(xb, xa, mp_t)
    res.sort(reverse=True)
    for i in range(len(res)):
        k = n-res[i]
        if(k >= n):
            continue
        x = a[k] ^ b[0]
        print(str(k) + ' ' + str(x))


main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class RollingHash():
    def __init__(self, s):
        self.length = len(s)
        self.base = 1009
        self.mod = (1 << 61) - 1
        self.hash = [0] * (self.length + 1)
        self.pow = [1] * (self.length + 1)

        for i in range(self.length):
            self.hash[i+1] = (self.hash[i] + s[i]) * self.base % self.mod
            self.pow[i+1] = self.pow[i] * self.base % self.mod

    def get(self, l, r):
        t = self.hash[r] - self.hash[l] * self.pow[r-l] % self.mod
        t = (t + self.mod) % self.mod
        return t

n = int(input())
a = [int(item) for item in input().split()]
b = [int(item) for item in input().split()]
a = a + a

diffa = []
diffb = []
for i in range(1, len(a)):
    diffa.append(a[i] ^ a[i-1])
for i in range(1, len(b)):
    diffb.append(b[i] ^ b[i-1])

RHa = RollingHash(diffa)
RHb = RollingHash(diffb)
query = RHb.get(0, n-1)
ans = []
for i in range(n):
    val = RHa.get(i, i+n-1)
    if val == query:
        ans.append((i, a[i] ^ b[0]))
ans.sort()
for k, x in ans:
    print(k, x)

Submission status: Accepted

Solution code:
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    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
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + [-1] + BB + BB)
for i in range(N, 0, -1):
    if T[N+i+1] >= N:
        print(N-i, A[-i%N] ^ B[0])

Submission status: Accepted

Solution code:
def KMP_table(WW):
    TT = [-1] * (len(WW)+2)
    ii = 2
    jj = 0
    TT[0] = -1
    TT[1] = 0
    while ii < len(WW)+1:
        if WW[ii - 1] == WW[jj]:
            TT[ii] = jj + 1
            ii += 1
            jj += 1
        elif jj > 0:
            jj = TT[jj]
        else:
            TT[ii] = 0
            ii += 1
    return TT

def KMP(T):
    ret = -1
    
    m = 0
    i = 0
    RE = []
    while m + i < len(S):
        if W[i] == S[m + i]:
            i += 1
            if i == len(W):
                RE.append(m)
                m = m + i - T[i]
                if i > 0:
                    i = T[i]
        else:
            m = m + i - T[i]
            if i > 0:
                i = T[i]
    return RE

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
S = ([A[i] ^ A[i-1] for i in range(N)] * 2)[:-1]
W = [B[i] ^ B[i-1] for i in range(N)]

T = KMP_table(W)
for i in KMP(T):
    print(i, A[i] ^ B[0])

Submission status: Accepted

Solution code:
def Z_algorithm(s):
    n = len(s)
    A = [n] + [0] * (n-1)
    i, j = 1, 0
    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
    return A

N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]

T = Z_algorithm(AA + BB + BB)
for i in range(N, 0, -1):
    if T[N+i] >= N:
        print(N-i, A[-i%N] ^ B[0])

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]
P = 8128812823
K = 8128
invK = pow(K, P-2, P)
KN = pow(K, N, P)

s = 0
for i in range(N):
    s = (s * K + AA[i]) % P

t = 0
for b in BB:
    t = (t * K + b) % P
ans = 0
for i in range(N)[::-1]:
    if t == s:
        j = N - 1 - i
        print(j, A[j] ^ B[0])
    t = (t + BB[i] * (KN - 1)) * invK % P

Submission status: Accepted

Solution code:
N = int(input())
A = [int(a) for a in input().split()]
B = [int(a) for a in input().split()]
AA = [A[i] ^ A[i-1] for i in range(N)]
BB = [B[i] ^ B[i-1] for i in range(N)]
P = 8128812881288171
K = 8128
invK = pow(K, P-2, P)
KN = pow(K, N, P)

s = 0
for i in range(N):
    s = (s * K + AA[i]) % P

t = 0
for b in BB:
    t = (t * K + b) % P
ans = 0
for i in range(N)[::-1]:
    if t == s:
        j = N - 1 - i
        print(j, A[j] ^ B[0])
    t = (t + BB[i] * (KN - 1)) * invK % P

Submission status: Accepted

Solution code:
def solve(n, aaa, bbb):
    ccc = [a1 ^ a2 for a1, a2 in zip(aaa, aaa[1:])] + [aaa[-1] ^ aaa[0]]
    ddd = [b1 ^ b2 for b1, b2 in zip(bbb, bbb[1:])] + [bbb[-1] ^ bbb[0]]

    ans = []

    m = 2147483647
    g = 1000000007
    s = 0
    for c in ccc:
        s = (s * g + c) % m
    t = 0
    for d in ddd:
        t = (t * g + d) % m
    u = pow(g, n, m) - 1
    for i in range(n):
        if s == t:
            ans.append((i, aaa[i] ^ bbb[0]))
        s = (s * g - ccc[i] * u) % m
    ans.sort()
    return ans


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
ans = solve(n, aaa, bbb)
print(''.join('{} {}\n'.format(*answer) for answer in ans))

Submission status: Accepted

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

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)]
C = C + C[:-1]
K = KMP(D).search(C)
#C string D pattern
for k in K:
    print(k, A[k]^B[0])

Submission status: Accepted

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

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)]
C = C + C[:-1]
K = KMP(D).search(C)
#D string C pattern
for k in K:
    print(k, A[k]^B[0])

Submission status: Accepted

Solution code:
class KMP:
    def __init__(self, P):
        self.P = P
        self.N = len(P)
        self.T = [0] * (self.N + 1)
        self._compile()

    def _compile(self):
        j = 0
        self.T[0] = -1
        for i in range(1, self.N):
            self.T[i] = j
            j += 1 if self.P[i] == self.P[j] else -j
        self.T[self.N] = j

    def search(self, S):
        NS = len(S)
        i = m = 0
        A = []
        while m + i < NS:
            if self.P[i] == S[m + i]:
                i += 1
                if i != self.N:
                    continue
                A.append(m)
            m += i - self.T[i]
            i = max(0, self.T[i])
        return A

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)]
C = C + C[:-1]
K = KMP(D).search(C)
for k in K:
    print(k, A[k]^B[0])

Submission status: Accepted

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

AX=[A[i%N]^A[(i-1)%N] for i in range(N,0,-1)]
BX=[B[i%N]^B[(i-1)%N] for i in range(N,0,-1)]
BX2=BX+BX
#print(BX2)
#print(AX)

shift=[0]*(N+1)
k=1
l=0
while k<N:
    if AX[k]==AX[l]:
        k+=1
        l+=1
        shift[k]=l
    elif l>0:
        l=shift[l]
    else:
        k+=1
        shift[k]=0
#print(shift)

ans=[]
ai=bi=0
Z=0
while bi<N:
    #print(bi,ai)
    if BX2[bi+ai]==AX[ai]:
        ai+=1
        if ai==N-1:
            print(bi,A[bi]^B[0])
            ans.append((bi+1)%N)
            bi+=ai-shift[ai]
            ai=shift[ai]
    else:
        bi+=1 if ai==0 else ai-shift[ai]
        ai=shift[ai]

Submission status: Accepted

Solution code:
def z_algorithm(s):
    """文字列sが与えられたとき、各iについて「SとS[i:|S|-1]の最長共通接頭辞の長さ」
    を記録した配列 A を O(|S|) で構築するアルゴリズムです。"""

    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a


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

p = [0] * n
q = [0] * n
for i in range(n):
    p[i] = a[i] ^ a[(i + 1) % n]
    q[i] = b[i] ^ b[(i + 1) % n]

test = q + p + p
res = z_algorithm(test)
ans = []
for i in range(n, 2*n):
    if res[i] >= n:
        ans.append((i - n, a[(i - n) % n] ^ b[0]))
ans = sorted(ans)

for i in ans:
    print(*i)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of 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


def main():
    n = int(input())
    a = tuple(map(int,input().split()))
    b = tuple(map(int,input().split()))


    BAA = []
    for i in range(n-1):
        BAA.append(b[i]^b[i+1])
    BAA.append(b[0]^b[-1])

    BAA.append(-1)

    for i in range(n-1):
        BAA.append(a[i]^a[i+1])
    BAA.append(a[0]^a[-1])
    for i in range(n-1):
        BAA.append(a[i]^a[i+1])
    BAA.append(a[0]^a[-1])

    z = Z_algorithm(BAA)

    for k in range(n):
        if z[n+k+1] >= n:
            print(k,b[0]^a[k])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

#Z[i]:length of the longest list starting from S[i] which is also a prefix of 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 = tuple(map(int,input().split()))
b = tuple(map(int,input().split()))


BAA = []
for i in range(n-1):
    BAA.append(b[i]^b[i+1])
BAA.append(b[0]^b[-1])

BAA.append(-1)

for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])
for i in range(n-1):
    BAA.append(a[i]^a[i+1])
BAA.append(a[0]^a[-1])

z = Z_algorithm(BAA)

for k in range(n):
    if z[n+k+1] >= n:
        print(k,b[0]^a[k])

Submission status: Accepted

Solution code:
n = int(input())
##実装ミスをあとでミスっていたことが分かるよう修正した結果a,b逆。
##要注意
b = list(map(int, input().split( )))
a = list(map(int,input().split( )))

#これでx考慮しなくてよくなる
a2 = [a[i]^a[i-1] for i in range(n)]
b2 = [b[i]^b[i-1] for i in range(n)]
b2 = b2+b2
#print(a2)
#print(b2)

#ローリングハッシュ
#https://tjkendev.github.io/procon-library/python/string/rolling_hash.html

base = 37; mod = 10**9 + 9
pw = None
def rolling_hash(s):
    l = len(s)
    h = [0]*(l + 1)
    v = 0
    for i in range(l):
        h[i+1] = v = (v * base + s[i]) % mod
    return h
# RH前に、必要な長さの最大値分のpow-tableを計算しておく
def setup_pw(l):
    global pw
    pw = [1]*(l + 1)
    v = 1
    for i in range(l):
        pw[i+1] = v = v * base % mod
def get(h, l, r):#lは含まない
    return (h[r] - h[l] * pw[r-l]) % mod

setup_pw(n*2)
bh = rolling_hash(b2)
ah = rolling_hash(a2)
ans = []

get_a = get(ah,0,n)
for k in range(n):
    if get(bh,k,k+n) == get_a:
        ans.append(k)
for k in ans:
    x = b[k]^a[0]
    print(k,x)