Submission #874224

#TimeUsernameProblemLanguageResultExecution timeMemory
874224vjudge1Necklace (Subtask 1-3) (BOI19_necklace1)C++17
25 / 85
1541 ms2824 KiB
#include <bits/stdc++.h> using namespace std; using i64 = long long; const int PRI = 41; const int MOD = 2000000011; int mul(int a, int b) { return (1LL * a * b) % MOD; } int add(int a, int b) { return (0LL + a + b) % MOD; } int stra[405][405], strb[405][405]; int reva[405][405], revb[405][405]; #define ONLINE_JUDGE void solve() { string a, b; cin >> a >> b; int n = int(a.size()), m = int(b.size()); for(int l = 0; l < n; l++) { int res = 0; for(int r = l; r < n; r++) { res = mul(res, PRI); res = add(res, (a[r] - 'a' +1)); stra[l][r] = res; } } for(int l = 0; l < m; l++) { int res = 0; for(int r = l; r < m; r++) { res = mul(res, PRI); res = add(res, (b[r] - 'a' +1)); strb[l][r] = res; } } for(int r = n -1; r >= 0; r--) { int res = 0; for(int l = r; l >= 0; l--) { res = mul(res, PRI); res = add(res, (a[l] - 'a' +1)); reva[l][r] = res; } } for(int len = min(n, m); len >= 1; len--) { for(int l = 0; l + len -1 < n; l++) { for(int r = 0; r + len -1 < m; r++) { for(int k = 0; k <= len; k++) { //string x = a.substr(l, len); //reverse(x.begin(), x.end()); //cerr << len << " -> " << x.substr(0, k) << " " << b.substr(r + len - k, k) << " :: " << x.substr(k, len - k) << " " << b.substr(r, len - k) << "\n"; //cerr << len << " -> " << reva[l + len - k][l + len -1] << " " << strb[r + len - k][r + len -1] << " :: " << reva[l][l + len - k -1] << " " << strb[r][r + len - k -1] << "\n"; if(reva[l + len - k][l + len -1] == strb[r + len - k][r + len -1] && reva[l][l + len - k -1] == strb[r][r + len - k -1]) { cout << len << "\n"; cout << l << " " << r << "\n"; return; } //cerr << len << " -> " << a.substr(l, k) << " " << b.substr(r + len - k, k) << " :: " << a.substr(l + k, len - k) << " " << b.substr(r, len - k) << "\n"; //cerr << len << " -> " << stra[l][l + k -1] << " " << strb[r + len - k][r + len -1] << " :: " << stra[l + k][l + len -1] << " " << strb[r][r + len - k -1] << "\n"; if(stra[l][l + k -1] == strb[r + len - k][r + len -1] && stra[l + k][l + len -1] == strb[r][r + len - k -1]) { cout << len << "\n"; cout << l << " " << r << "\n"; return; } } } } } cout << 0 << "\n"; cout << 0 << " " << 0 << "\n"; return; } signed main() { #ifndef ONLINE_JUDGE freopen(".in", "r", stdin); freopen(".out", "w", stdout); #endif ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int t = 1; //cin >> t; for(int i = 1; i <= t; i++) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...