Untitled
unknown
plain_text
a year ago
2.0 kB
5
Indexable
#include <iostream> #include <vector> #include <algorithm> #include <map> #include <set> #include <queue> #include <stack> #include <cmath> #include <cstring> #include <string> #include <climits> #include <ctime> #define FOU(i, a, b) for(int i = (a); i <= (b); i++) // for up #define FOD(i, a, b) for(int i = (a); i >= (b); i--) // for down #define FOA(i, n) for(int i = 0; i < (n); i++) // for array #define TIME (1.0 * clock() / CLOCKS_PER_SEC) using namespace std; typedef long long ll; const ll base = 100003; const ll MOD = 1000000007; // 10^9 + 7 ll n, m, a[1001], b[1001], k = 0, p = -1, q = -1; ll tmp; ll POW[1001], hashA[1001], hashB[1001]; map<ll, int> ma; ll getHashA(int i, int j){ return (hashA[j] - hashA[i-1] * POW[j-i+1] + MOD*MOD) % MOD; } ll getHashB(int i, int j){ return (hashB[j] - hashB[i-1] * POW[j-i+1] + MOD*MOD) % MOD; } void giao(ll a[], int n, ll b[], int m){ POW[0] = 1; hashA[0] = hashB[0] = 0; for(int i = 1; i <= m; i++) POW[i] = (POW[i-1] * base) % MOD; for(int i = 1; i <= n; i++) hashA[i] = (hashA[i-1] * base + a[i]) % MOD; for(int i = 1; i <= m; i++) hashB[i] = (hashB[i-1] * base + b[i]) % MOD; for(int i = 1; i <= n; i++){ for(int j = i; j <= n; j++) ma[getHashA(i,j)] = i; } for(int j = m; j >= 1; j--){ for(int i = j; i >= 1; i--){ tmp = ma[getHashB(i,j)]; if(tmp){ if(j-i+1 > k){ k = j-i+1; p = tmp; q = i; } } } } cout << k << " " << p << " " << q << endl; } int main(){ // 1<=n,m<=1000 1<=ai,bi<=10^5 ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); freopen("test.inp","r",stdin); freopen("test.out","w",stdout); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; cin >> m; for(int i = 1; i <= m; i++) cin >> b[i]; if(n > m) giao(b,m,a,n); else giao(a,n,b,m); cerr << "Time elapsed: " << TIME << " s.\n"; return 0; }
Editor is loading...
Leave a Comment