#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ld long double
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define SZ(x) (int)(x).size()
template <typename T> using ord_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int n0 = 2003, inf = 1e9;
struct T {
int len, d1, d2;
void clean() {
len = 0, d1 = 0, d2 = 0;
}
void upd(const T & t) {
if (t.len + 1 > len || (t.len == len && (t.len == 0 || t.d1 < d1 || t.d2 + 1 < d2))) {
len = t.len + 1;
if (t.len > 0) {
d1 = t.d1;
d2 = t.d2 + 1;
} else {
d1 = 0, d2 = 0;
}
}
}
void mx(const T & t) {
if (t.len > len || (t.len == len && (t.len == 0 || t.d1 < d1 || t.d2 + 1 < d2))) {
len = t.len;
if (t.len > 0) {
d1 = t.d1;
d2 = t.d2 + 1;
} else {
d1 = 0, d2 = 0;
}
}
}
};
T dp[n0];
int LCS(const string & a, const string & b) {
int n = SZ(a), m = SZ(b);
for (int j = 1; j <= m; j++)
dp[j].clean();
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 1; j--) {
if (dp[j].len > 0) dp[j].d1++;
if (a[i - 1] == b[j - 1])
dp[j].upd(dp[j - 1]);
}
for (int j = 1; j <= m; j++)
dp[j].mx(dp[j - 1]);
for (int j = 1; j <= m; j++)
if (dp[j].d1 >= n / 2 || dp[j].d2 >= m / 2)
dp[j].clean();
}
int res = 0;
for (int j = 1; j <= m; j++) {
res = max(res, dp[j].len);
}
return res;
}
int main() {
ios_base::sync_with_stdio(false), cin.tie(NULL);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
#endif
string a, b, A, B;
cin >> a >> b;
int res = 0;
for (int i = 0; i < 4; i++) {
A = a, B = b;
if (i & 1) reverse(all(A));
if (i & 2) reverse(all(B));
A += A, B += B;
res = max(res, LCS(A, B));
}
cout << res;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
384 KB |
Output isn't correct |
| 2 |
Correct |
1 ms |
384 KB |
Output is correct |
| 3 |
Correct |
0 ms |
384 KB |
Output is correct |
| 4 |
Correct |
1 ms |
384 KB |
Output is correct |
| 5 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
| 6 |
Correct |
11 ms |
384 KB |
Output is correct |
| 7 |
Correct |
91 ms |
384 KB |
Output is correct |
| 8 |
Incorrect |
159 ms |
420 KB |
Output isn't correct |
| 9 |
Incorrect |
148 ms |
424 KB |
Output isn't correct |
| 10 |
Incorrect |
128 ms |
384 KB |
Output isn't correct |
| 11 |
Incorrect |
121 ms |
384 KB |
Output isn't correct |
| 12 |
Correct |
108 ms |
384 KB |
Output is correct |
| 13 |
Incorrect |
182 ms |
384 KB |
Output isn't correct |
| 14 |
Incorrect |
143 ms |
416 KB |
Output isn't correct |
| 15 |
Incorrect |
152 ms |
420 KB |
Output isn't correct |
| 16 |
Incorrect |
177 ms |
384 KB |
Output isn't correct |
| 17 |
Incorrect |
94 ms |
384 KB |
Output isn't correct |
| 18 |
Incorrect |
156 ms |
504 KB |
Output isn't correct |
| 19 |
Incorrect |
113 ms |
416 KB |
Output isn't correct |
| 20 |
Incorrect |
178 ms |
384 KB |
Output isn't correct |
| 21 |
Incorrect |
39 ms |
384 KB |
Output isn't correct |
| 22 |
Incorrect |
62 ms |
412 KB |
Output isn't correct |
| 23 |
Incorrect |
75 ms |
408 KB |
Output isn't correct |
| 24 |
Incorrect |
75 ms |
384 KB |
Output isn't correct |
| 25 |
Incorrect |
101 ms |
384 KB |
Output isn't correct |
