#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3005;
using lint = long long;
using pi = pair<lint, int>;
struct dap{
int x, y, z;
bool operator<(const dap &d)const{
return z < d.z;
}
};
int n, m;
string s, t;
int lcp[MAXN][MAXN];
dap solve(){
for(int i=n-1; i>=0; i--){
for(int j=m-1; j>=0; j--){
if(s[i] == t[j]) lcp[i][j] = lcp[i+1][j+1] + 1;
else lcp[i][j] = 0;
}
}
dap ret = {-1, -1, -1};
for(int i=0; i<=n; i++){
for(int j=0; j<=m; j++){
int minsx = 1e9;
int minsy = 1e9;
for(int sy = 0; sy <= j; sy++){
if(lcp[i][sy] + sy >= j){
minsy = sy;
break;
}
}
for(int sx = 0; sx <= i; sx++){
if(lcp[sx][j] + sx >= i){
minsx = sx;
break;
}
}
ret = max(ret, (dap){minsx, minsy, i + j - minsx - minsy});
}
}
return ret;
}
int main(){
cin >> s >> t;
n = s.size();
m = t.size();
auto ret = solve();
reverse(t.begin(), t.end());
auto y = solve();
y.y = m - y.y - y.z;
ret = max(ret, y);
cout << ret.z << endl;
cout << ret.x << " " << ret.y << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
760 KB |
Output is correct |
2 |
Correct |
4 ms |
760 KB |
Output is correct |
3 |
Correct |
4 ms |
632 KB |
Output is correct |
4 |
Correct |
4 ms |
760 KB |
Output is correct |
5 |
Correct |
4 ms |
760 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
760 KB |
Output is correct |
2 |
Correct |
4 ms |
760 KB |
Output is correct |
3 |
Correct |
4 ms |
632 KB |
Output is correct |
4 |
Correct |
4 ms |
760 KB |
Output is correct |
5 |
Correct |
4 ms |
760 KB |
Output is correct |
6 |
Correct |
77 ms |
2644 KB |
Output is correct |
7 |
Correct |
98 ms |
2552 KB |
Output is correct |
8 |
Correct |
96 ms |
2428 KB |
Output is correct |
9 |
Correct |
117 ms |
2428 KB |
Output is correct |
10 |
Correct |
131 ms |
2680 KB |
Output is correct |
11 |
Correct |
134 ms |
2552 KB |
Output is correct |
12 |
Correct |
111 ms |
2424 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
760 KB |
Output is correct |
2 |
Correct |
4 ms |
760 KB |
Output is correct |
3 |
Correct |
4 ms |
632 KB |
Output is correct |
4 |
Correct |
4 ms |
760 KB |
Output is correct |
5 |
Correct |
4 ms |
760 KB |
Output is correct |
6 |
Correct |
77 ms |
2644 KB |
Output is correct |
7 |
Correct |
98 ms |
2552 KB |
Output is correct |
8 |
Correct |
96 ms |
2428 KB |
Output is correct |
9 |
Correct |
117 ms |
2428 KB |
Output is correct |
10 |
Correct |
131 ms |
2680 KB |
Output is correct |
11 |
Correct |
134 ms |
2552 KB |
Output is correct |
12 |
Correct |
111 ms |
2424 KB |
Output is correct |
13 |
Execution timed out |
1554 ms |
35564 KB |
Time limit exceeded |
14 |
Halted |
0 ms |
0 KB |
- |