#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3010;
int dpsufsuf[MAXN][MAXN], dpprefsuf[MAXN][MAXN];
string a, b;
int ans, ians, jans;
void fazdp(int isrev){
int t1 = a.length();
int t2 = b.length();
t1--;
t2--;
for(int i = t1; i ; i--){
for(int j = t2; j; j--){
if(a[i] == b[j]){
dpsufsuf[i][j] = 1 + dpsufsuf[i+1][j+1];
}
}
}
for(int i = t1; i ; i--){
for(int j = t2; j; j--){
if(a[i] == b[j]){
dpprefsuf[i + dpsufsuf[i][j] - 1][j] = max(dpprefsuf[i + dpsufsuf[i][j] - 1][j], dpsufsuf[i][j]);
}
}
}
for(int i = 1; i <= t1; i++){
for(int j = 1; j <= t2; j++){
if(dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j] > ans){
if(!isrev) jans = j;
else{
jans = t2 - (j + dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j] - 1) + 1;
}
ians = i - dpprefsuf[i-1][j + dpsufsuf[i][j]];
ans = dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j];
}
}
}
}
int main(){
cin >> a;
a = '0' + a;
cin >> b;
b = '0' + b;
fazdp(0);
reverse(b.begin(), b.end());
fazdp(1);
cout << ans << endl;
cout << ians << ' ' << jans << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
1152 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
