Untitled
unknown
plain_text
a year ago
2.0 kB
8
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