#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";
}
string reversed(string x) {
reverse(x.begin(), x.end());
return x;
}
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;
int n = s.size(), m = t.size();
s = " " + s;
t = " " + 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=2; i<=n; i++) {
string u;
u += s.substr(i, n - i + 1);
u += "?";
u += t.substr(1, m); // ~ 6000
vector<int> lpsu = prefix_function(u);
string v;
v += reversed(s.substr(1, i-1));
v += "?";
v += reversed(t.substr(1, m));
vector<int> lpsv = prefix_function(v);
for(int j=1; j<m; j++) { // take [1, j]
// j = 1: n - i + 2
// j = x: n - i + x + 1 (0 based)
int suf = lpsu[n-i+j+1];
int pre = lpsv[i+m-j-1];
// answer = pre + suf
int inds = i - pre;
int indt = j - suf + 1;
upd_ans(pre + suf, inds, indt);
}
}
reverse(t.begin() + 1, t.end());
for(int i=2; i<=n; i++) {
string u;
u += s.substr(i, n - i + 1);
u += "?";
u += t.substr(1, m); // ~ 6000
vector<int> lpsu = prefix_function(u);
string v;
v += reversed(s.substr(1, i-1));
v += "?";
v += reversed(t.substr(1, m));
vector<int> lpsv = prefix_function(v);
/*
cout << u << "\n";
for(int x: lpsu) cout << x << " ";
cout << "\n";
cout << v << "\n";
for(int x: lpsv) cout << x << " ";
cout << "\n";
*/
for(int j=1; j<m; j++) { // take [1, j]
// j = 1: n - i + 2
// j = x: n - i + x + 1 (0 based)
int suf = lpsu[n-i+j+1];
int pre = lpsv[i+m-j-1];
// answer = pre + suf
int inds = i - pre;
int indt = j + pre;
indt = m - indt + 1;
upd_ans(pre + suf, inds, indt);
}
}
reverse(t.begin() + 1, t.end());
// Remove whitespace
s = s.substr(1, n);
t = t.substr(1, m);
// 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) m - 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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
314 ms |
644 KB |
Output is correct |
| 2 |
Correct |
271 ms |
592 KB |
Output is correct |
| 3 |
Correct |
517 ms |
664 KB |
Output is correct |
| 4 |
Correct |
319 ms |
492 KB |
Output is correct |
| 5 |
Correct |
187 ms |
576 KB |
Output is correct |
| 6 |
Correct |
322 ms |
668 KB |
Output is correct |
| 7 |
Correct |
276 ms |
628 KB |
Output is correct |
| 8 |
Correct |
294 ms |
624 KB |
Output is correct |
| 9 |
Correct |
263 ms |
604 KB |
Output is correct |
