#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];
ar<int, 3> solve(string a, string b){
memset(is, 0, sizeof is);
memset(d, 0, sizeof d);
memset(u, 0, sizeof u);
memset(ur, 0, sizeof ur);
memset(dl, 0, sizeof dl);
ar<int, 3> res {};
int n = a.size(), m = b.size();
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);
}
}
//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<m;j++){
//~ cout<<ur[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
//~ for(int i=0;i<n;i++){
//~ for(int j=0;j<m;j++){
//~ cout<<dl[i][j]<<" ";
//~ } cout<<"\n";
//~ } cout<<"\n";
for(int i=0;i+1<n;i++){
for(int j=1;j<m;j++){
//~ cout<<i<<" "<<j<<" "<<ur[i][j] + dl[i+1][j-1]<<" "<<i - ur[i][j] + 1<<" "<<j - dl[i+1][j-1]<<"\n";
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 = solve(a, b);
tt[2] = (int)b.size() - tt[1] - 1;
//~ cout<<res[0]<<" "<<res[1]<<" "<<res[2]<<"\n";
//~ cout<<tt[0]<<" "<<tt[1]<<" "<<tt[2]<<"\n";
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 |
Incorrect |
64 ms |
176900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
176900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
64 ms |
176900 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
