#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3010;
int dpsufsuf[MAXN][MAXN], dpprefsuf[MAXN][MAXN];
char a[MAXN], b[MAXN];
int ans, ians, jans;
void fazdp(int isrev){
int t1 = strlen(a + 1);
int t2 = strlen(b + 1);
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];
dpprefsuf[i + dpsufsuf[i][j] - 1][j] = max(dpprefsuf[i + dpsufsuf[i][j] - 1][j], dpsufsuf[i][j]);
}
}
}
// for(int i = t1; i ; i--){
// for(int j = t2; j; j--){
// if(a[i] == b[j]){
// }
// }
// }
for(int i = 1; i <= t1; i++){
for(int j = 1; j <= t2; j++){
int v = dpsufsuf[i][j] + dpprefsuf[i-1][dpsufsuf[i][j] + j];
if( v > ans){
if(!isrev) jans = j;
else{
int aux = j + v -1;
jans = t2 - aux + 1;
}
ians = i - dpprefsuf[i-1][j + dpsufsuf[i][j]];
ans = v;
}
}
}
}
int main(){
cin >>( a + 1);
//a = '0' + a;
cin >> (b + 1);
//b = '0' + b;
fazdp(0);
int st = strlen(b + 1);
//cout << b +1;
for(int i = 1, j = st; i < j; i++, j--){
swap(b[i], b[j]);
}
memset(dpsufsuf, 0 , sizeof(dpsufsuf));
memset(dpprefsuf, 0 , sizeof(dpprefsuf));
//cout << b + 1;
fazdp(1);
cout << ans << endl;
cout << ians -1<< ' ' << jans -1 << endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
140 ms |
65540 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
