答案在哪里

全部评论 1

• 

  蜜果

  

  #include<bits/stdc++.h>
  typedef long long ll;
  typedef unsigned long long ull;
  typedef stdpair<int, int> PII;
  typedef stdpair<ll, ll> PLL;
  typedef double db;
  #define arr(x) (x).begin(),(x).end()
  #define x first
  #define y second
  #define pb push_back
  #define mkp make_pair
  #define endl "\n"
  using namespace std;
  const int N = 2e5 + 10;
  int ne[2 * N], n, ans = 0;

  void get_ne(vector<int>& s){
  int len = 2 * n;
  ne[1] = 0;
  for(int i = 2, j = 0; i <= len; i++){
  while(j && s[j + 1] != s[i]) j = ne[j];
  if(s[i] == s[j + 1]) j++;
  ne[i] = j;
  }
  }

  vector<int> Match(vector<int>& s, vector<int>& p){
  int lens = 2 * n - 1, lenp = n;
  vector<int> res;
  for(int i = 1, j = 0; i <= lens; i++){
  while(j && s[i] != p[j + 1]) j = ne[j];
  if(s[i] == p[j + 1]) j++;
  if(j == lenp){
  res.pb(i - n);
  ans++;
  j = ne[j];
  }
  }
  return res;
  }

  int main(){
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  vector<int> a(2 * n + 1, 0), xa(n + 1, 0);
  vector<int> b(n + 1, 0), xb(n + 1, 0);
  for(int i = 1; i <= n; i++)
  cin >> xa[i];
  for(int i = 1; i <= n; i++)
  cin >> xb[i];
  for(int i = 1; i <= n; i++){
  if(i != n){
  a[i] = xa[i] ^xa[i + 1];
  b[i] = xb[i] ^ xb[i + 1];
  }
  else{
  a[i] = xa[i] ^ xa[1];
  b[i] = xb[i] ^ xb[1];
  }
  a[i + n] = a[i];
  }
  get_ne(a);
  auto res = Match(a, b);
  for(auto k: res){
  cout << k << " " << (xb[1] ^ xa[1 + k]) << endl;
  }
  return 0;
  }

  3天前 来自 山东

  0