解法

別解たくさんだったので。私は乱択派

想定解: 階差

$a _ {k + i} \oplus x = b _ i$ かつ $a _ {k + i + 1} \oplus x = b _ {i + 1}$ なので $a _ {k + i} \oplus a _ {k + i + 1} = b _ i \oplus b _ {i + 1}$ である。$a$ の階差と $b$ の階差をそれぞれ取って一致するように回転させればその回転量が所望の $k$ である。$O(N)$。それはそうだけど天才か？

非想定: 乱択

$k$ を固定すると (その時点で) 唯一の候補である $x = a _ {k + i} \oplus b _ i$ がひとつ得られる。 すべての $j$ について $x = a _ {k + j} \oplus b _ j$ であるか判定すればよい。 これをすべての $j$ についてでなく適当な $K = 100$ 個ぐらいとやれば間に合いがち。$O(NK)$。

ただし、とりあえず思い付く乱択対策が $a = (0, 0, 0, \dots, 0)$ で $b = (0, 0, 0, \dots, 0, 1, 0, 0, 0, \dots, 0)$ みたいなやつで、この乱択対策の対策ぐらいはしておく必要がありそう。

非想定: rolling hash

bit ごとに独立に rolling hash (あるいは KMP 法でもよい) をしてその $k$ の共通部分を取る。bit 数 $B = 30$ が乗って $O(NB)$。

非想定: 枝刈り

メモ