#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef int64_t ll;
//~ #define int ll
const int N = 3005;
//~ int is[N][N], d[N][N], u[N][N], ur[N][N], dl[N][N];
int pref[N], suff[N];
ar<int, 3> solve(string a, string b){
//~ memset(is, 0, sizeof is);
//~ memset(u, 0, sizeof u);
//~ memset(d, 0, sizeof d);
ar<int, 3> res {};
int n = a.size(), m = b.size();
//~ cout<<a<<"\n"<<b<<"\n";
deque<ar<int, 2>> ns(n);
for(int j=0;j<m;j++){
ns.push_front({0, 0});
for(int i=0;i<=n;i++){
if(ns[i][1]) ns[i][1]--, ns[i][0]++;
else ns[i][0] = 0;
if(a[i] == b[j] && ns[i][1] == 0){
for(int k=0;i + k < n && j + k < m && a[i + k] == b[j + k]; k++){
ns[i][1]++;
}
}
}
//~ for(int i=0;i<=n;i++){
//~ d[i][j] = ns[i][1];
//~ u[i][j] = ns[i][0];
//~ }
memset(pref, 0, sizeof pref);
memset(suff, 0, sizeof suff);
for(int i=0;i<=n;i++){
pref[i - ns[i][0]] = max(pref[i - ns[i][0]], ns[i][0]);
if(ns[i][1]){
suff[i + ns[i][1] - 1] = max(suff[i + ns[i][1] - 1], ns[i][1]);
}
}
for(int i=1;i<=n;i++){
pref[i] = max(pref[i], pref[i-1] - 1);
}
for(int i=n-1;~i;i--){
suff[i] = max(suff[i], suff[i+1] - 1);
}
//~ for(int i=0;i<=n;i++){
//~ cout<<pref[i]<<" ";
//~ } cout<<"\n";
//~ for(int i=0;i<=n;i++){
//~ cout<<suff[i]<<" ";
//~ } cout<<"\n\n";
for(int i=0;i<n;i++){
res = max(res, {pref[i + 1] + suff[i], i - suff[i] + 1, j - pref[i + 1]});
}
ns.pop_back();
}
//~ for(int i=0;i<=n;i++){
//~ for(int j=0;j<m;j++){
//~ cout<<d[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int i=0;i<=n;i++){
//~ for(int j=0;j<m;j++){
//~ cout<<u[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<m;j++){
//~ if(a[i] == b[j]){
//~ is[i][j] = d[i][j] = u[i][j] = 1;
//~ }
//~ }
//~ }
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<m;j++){
//~ if(i && j && is[i][j]) u[i][j] += u[i-1][j-1];
//~ res = max(res, {u[i][j], i - u[i][j] + 1, j - u[i][j] + 1});
//~ }
//~ }
//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
//~ for(int i=n-1;~i;i--){
//~ for(int j=m-1;~j;j--){
//~ if(is[i][j]) d[i][j] += d[i+1][j+1];
//~ }
//~ }
//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<m;j++){
//~ cout<<is[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<m;j++){
//~ if(!is[i][j]) continue;
//~ assert(j + 1 >= u[i][j]);
//~ ur[i][j - u[i][j] + 1] = max(ur[i][j - u[i][j] + 1], u[i][j]);
//~ dl[i][j + d[i][j] - 1] = max(dl[i][j + d[i][j] - 1], d[i][j]);
//~ }
//~ for(int j=1;j<m;j++){
//~ ur[i][j] = max(ur[i][j], ur[i][j-1] - 1);
//~ }
//~ for(int j=m-1;~j;j--){
//~ dl[i][j] = max(dl[i][j], dl[i][j+1] - 1);
//~ }
//~ }
//~ for(int i=0;i+1<n;i++){
//~ for(int j=1;j<m;j++){
//~ res = max(res, {ur[i][j] + dl[i+1][j-1], i - ur[i][j] + 1, j - dl[i+1][j-1]});
//~ }
//~ }
return res;
}
/*
qhagio
cqyqkzb
mzmxnzw
xuefnx
*/
signed main(){
ios::sync_with_stdio(0); cin.tie(0);
string a, b; cin>>a>>b;
ar<int, 3> res {};
res = solve(a, b);
reverse(b.begin(), b.end());
ar<int, 3> tt {};
tt = solve(a, b);
tt[2] = (int)b.size() - tt[2] - tt[0];
res = max(res, tt);
if(!res[0]){
cout<<0<<"\n";
return 0;
}
//~ assert(res[0]);
cout<<res[0]<<"\n";
cout<<res[1]<<" "<<res[2]<<"\n";
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
536 ms |
372 KB |
Output is correct |
| 2 |
Correct |
483 ms |
376 KB |
Output is correct |
| 3 |
Correct |
555 ms |
368 KB |
Output is correct |
| 4 |
Correct |
437 ms |
340 KB |
Output is correct |
| 5 |
Correct |
414 ms |
440 KB |
Output is correct |
| 6 |
Correct |
454 ms |
328 KB |
Output is correct |
| 7 |
Correct |
486 ms |
384 KB |
Output is correct |
| 8 |
Correct |
498 ms |
376 KB |
Output is correct |
| 9 |
Correct |
508 ms |
368 KB |
Output is correct |
