Untitled

 avatar
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