#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define F first
#define S second
#define pb push_back
#define endl "\n"
#define all(x) x.begin(), x.end()
const int M = 3005;
const ll inf = 1e18;
const ll mod = 998244353;
const double pi = acos(-1);
const int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
array <int, 3> solve (string s, string t){
int n = s.size(), m = t.size();
array <int, 3> ret;
int dpS[M][M] = {0};
int dpPS[M][M] = {0};
int dpSP[M][M] = {0};
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j)
if(s[i] == t[j])
dpS[i][j] = (i && j ? dpS[i - 1][j - 1] + 1 : 1);
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j) if(dpS[i][j]){
dpPS[i - dpS[i][j] + 1][j] = max(dpPS[i - dpS[i][j] + 1][j], dpS[i][j]);
dpSP[i][j - dpS[i][j] + 1] = max(dpSP[i][j - dpS[i][j] + 1], dpS[i][j]);
}
for(int i = 0; i < n; ++i)
for(int j = 0; j < m; ++j){
if(i) dpPS[i][j] = max(dpPS[i][j], dpPS[i - 1][j] - 1);
if(j) dpSP[i][j] = max(dpSP[i][j], dpSP[i][j - 1] - 1);
}
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
int len = dpSP[i][j];
if(i < n && j) len += dpPS[i + 1][j - 1];
if(len > ret[0]){
ret[0] = len;
ret[1] = i - dpSP[i][j] + 1;
ret[2] = j + dpSP[i][j] - len;
}
}
}
return ret;
}
int main()
{
string s, t;
cin >> s >> t;
array <int, 3> ans = solve(s, t);
reverse(all(t));
array <int, 3> tmp = solve(s, t);
tmp[2] = t.size() - tmp[2] - tmp[0];
ans = max(ans, tmp);
cout << ans[0] << endl << ans[1] << " " << ans[2] << endl;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
106292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
106292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
66 ms |
106292 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
