fork download
copy 
  1. #include <bits/stdc++.h> // NeOWami
  2. using namespace std;
  3.  
  4. #define ft first
  5. #define sc second
  6. #define int long long
  7. const int N = 1e3 + 5;
  8. const int BASE = 2e3 + 3;
  9.  
  10. using dbhash = pair<int, int>;
  11. const int MOD1 = 1e9 + 7, MOD2 = 1e9 + 307;
  12. const int inf = 1e18 + 2;
  13. const int NeOWami = 2008050720080507;
  14. int getHash(int x) {
  15.     return (x + inf) ^ NeOWami;
  16. }
  17. dbhash hint(int x) {
  18.     return {getHash(x) % MOD1, getHash(x) % MOD2};
  19. }
  20. dbhash operator + (const dbhash& u, const dbhash& v) {
  21.     return {(u.first + v.first) % MOD1, (u.second + v.second) % MOD2};
  22. }
  23. dbhash operator - (const dbhash& u, const dbhash& v) {
  24.     return {(u.first - v.first + MOD1) % MOD1, (u.second - v.second + MOD2) % MOD2};
  25. }
  26.  
  27. int n, m, a[N], b[N], ans = 0;
  28. dbhash ha[N], hb[N];
  29. signed main() {
  30.     cin.tie(NULL)->sync_with_stdio(false);
  31.     if(ifstream("SIMILARITY.inp")) {
  32.         freopen("SIMILARITY.inp", "r", stdin);
  33.         freopen("SIMILARITY.out", "w", stdout);
  34.     }
  35.     cin >> n; for (int i = 1; i <= n; i++) cin >> a[i];
  36.     cin >> m; for (int i = 1; i <= m; i++) cin >> b[i];
  37.     ha[0] = hb[0] = {0, 0};
  38.     for (int i = 1; i <= n; i++) ha[i] = ha[i - 1] + hint(a[i]);
  39.     for (int i = 1; i <= m; i++) hb[i] = hb[i - 1] + hint(b[i]);
  40.     for (int len = min(n,m); len >= 1; len--) {
  41.         map<dbhash, int> cand;
  42.         for (int i = 1; i + len - 1 <= n; i++) cand[ha[i + len - 1] - ha[i - 1]] = i;
  43.         for (int i = 1; i + len - 1 <= m; i++) {
  44.             dbhash t = hb[i + len - 1] - hb[i - 1];
  45.             if (cand.count(t)) {
  46.                 int j = cand[t];
  47.                 cout << len << " " << j << " " << i;
  48.                 return 0;
  49.             }
  50.         }
  51.     }
  52.     cout << "0 -1 -1";
  53.     return 0;
  54. }
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0 -1 -1
https://ideone.com/0RCnP2
language:
C++14 (gcc 8.3)
created:
9 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!