#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3004;
const int MOD = 998244353;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
vector<int> prefix_function(string t) {
int n = t.size();
vector<int> lps(n);
lps[0] = 0;
for(int i=1; i<n; i++) {
int j = lps[i-1];
while(j > 0 && t[i] != t[j]) {
j = lps[j-1];
}
if(t[i] == t[j]) lps[i] = j+1;
else lps[i] = 0;
}
return lps;
}
int ans1, sst, tst;
int pows[6010];
int aa[6010], bb[6010];
const int factor = 2017;
int hasha(int l, int r) {
int qq = aa[l-1] * pows[r - l + 1];
qq %= MOD;
int given = aa[r] - qq;
if(given < 0) given = (MOD - (abs(given) % MOD)) % MOD;
else given %= MOD;
return given;
}
int hashb(int l, int r) {
int qq = bb[l-1] * pows[r - l + 1];
qq %= MOD;
int given = bb[r] - qq;
if(given < 0) given = (MOD - (abs(given) % MOD)) % MOD;
else given %= MOD;
return given;
}
pair<int, pair<int, int> > lcs(string a, string b) { // length, starting positions
int n = a.size(), m = b.size();
a = " " + a;
b = " " + b;
int dp[2][m+1];
for(int i=0; i<2; i++) for(int j=0; j<=m; j++) dp[i][j] = 0;
int ma = 0;
for(int i=1; i<=n; i++) {
for(int j=0; j<=m; j++) dp[i & 1][j] = 0;
for(int j=1; j<=m; j++) {
if(a[i] == b[j]) dp[i & 1][j] = dp[(i-1) & 1][j-1] + 1;
else dp[i & 1][j] = 0;
ma = max(ma, dp[i & 1][j]);
}
}
aa[0] = bb[0] = 0;
for(int i=1; i<=n; i++) aa[i] = (aa[i-1] * factor + a[i]) % MOD;
for(int i=1; i<=m; i++) bb[i] = (bb[i-1] * factor + b[i]) % MOD;
for(int i=1; i<=n-ma+1; i++) {
for(int j=1; j<=m-ma+1; j++) {
if(hasha(i, i+ma-1) == hashb(j, j+ma-1)) {
return {ma, {i, j} };
}
}
}
assert(false);
}
void upd_ans(int new_len, int new_sst, int new_tst) {
if(new_len > ans1) {
ans1 = new_len;
sst = new_sst;
tst = new_tst;
}
}
void out() {
cout << ans1 << "\n";
cout << sst - 1 << " " << tst - 1 << "\n";
}
void solve(int tc) {
pows[0] = 1;
for(int i=1; i<6010; i++) pows[i] = (pows[i-1] * factor) % MOD;
string s, t;
cin >> s >> t;
// Need to compute answer for both t and rev(t), both s and rev(s), for all suffixes of s and t
// Can't be more duliu
/*
for(int i=0; i<s.size(); i++) {
string u;
u += s.substr(i, s.size() - i);
u += "?";
u += t; // ~ 6000
vector<int> lps = prefix_function(u);
bool
}
*/
// Compute lcs of s and t
pair<int, pair<int, int> > res = lcs(s, t);
upd_ans(res.first, res.second.first, res.second.second);
// Compute lcs of s and rev(t)
reverse(t.begin(), t.end());
res = lcs(s, t);
upd_ans(res.first, res.second.first, (int) t.size() - res.second.second - res.first + 2);
reverse(t.begin(), t.end());
out();
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1; //cin >> t;
for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
24 ms |
488 KB |
Output is partially correct |
| 2 |
Partially correct |
28 ms |
488 KB |
Output is partially correct |
| 3 |
Partially correct |
143 ms |
560 KB |
Output is partially correct |
| 4 |
Partially correct |
89 ms |
468 KB |
Output is partially correct |
| 5 |
Partially correct |
56 ms |
468 KB |
Output is partially correct |
| 6 |
Partially correct |
103 ms |
468 KB |
Output is partially correct |
| 7 |
Partially correct |
82 ms |
472 KB |
Output is partially correct |
| 8 |
Partially correct |
51 ms |
464 KB |
Output is partially correct |
| 9 |
Partially correct |
37 ms |
388 KB |
Output is partially correct |
