AtCoder Beginner Contest 150 F - Xor Shift

問題ページ
関連する問題を一つ示す．
「数列 を 回巡回シフトしたときに に一致するような を求めろ．」
この問題はZalgorithmやKMP法やローリングハッシュなどで解くことができる．ここではZalgorithmによる解法を示す． (適当な区切り文字) と連結した数列を考える．この数列に対してZalgorithmを適用する．(0-originで) 文字目が，接頭辞と一致する長さが 以上であれば， 回巡回シフトしたとき に一致する．

は MOD で考えることとする．
は条件「 が全て等しい」と同値である．よって， であるような を求めることができればよい．
が混ざった式であるのが厄介なので変形して， が独立になるようにする．

とすると最初に示した問題に帰着できた．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
// 「SとS[i:|S|-1]の最長共通接頭辞の長さ」を記録した配列AをO(|S|)で構築する  
// aaabaaaab  
// 921034210  
vector<ll> Zalgo(vector<ll> s) {  
    vector<ll> v(s.size());  
    v[0] = s.size();  
    int i = 1, j = 0;  
    while (i < s.size()) {  
        while (i+j < s.size() && s[j] == s[i+j]) ++j;  
        v[i] = j;  
        if (j == 0) { ++i; continue;}  
        int k = 1;  
        while (i+k < s.size() && k+v[k] < j) v[i+k] = v[k], ++k;  
        i += k; j -= k;  
    }  
    return v;  
}  
  
int main(void) {  
    ll n;  
    cin >> n;  
    vector<ll> a(n), b(n);  
    REP(i, n) cin >> a[i];  
    REP(i, n) cin >> b[i];  
  
    vector<ll> A(a), B(b);  
    REP(i, n) {  
        A[i] = a[i] ^ a[(i+1)%n];  
        B[i] = b[i] ^ b[(i+1)%n];  
    }  
  
    vector<ll> v(3*n+1);  
    REP(i, n) v[i] = B[i];  
    v[n] = -1;  
    REP(i, n) {  
        v[n+1+i] = A[i];  
        v[2*n+1+i] = A[i];  
    }  
  
    auto ret = Zalgo(v);  
    vector<ll> ans;  
    FOR(i, n+1, 2*n+1) if(ret[i] >= n) ans.push_back(i-n-1);  
      
    REP(i, ans.size()) cout << ans[i] << " " << (a[ans[i]%n] ^ b[0]) << endl;  
  
    return 0;  
}