#include <bits/stdc++.h>
using namespace std;
/** so there is complicated algo based on some research let's get it later
*
*
* you have to get that |lcs(a, b) - lcs(a, b[1..n-1] + b[0])| <= 2
* so if you have ans >= lcs(a, b) + 2 then ... push it
* */
const int N = 2024;
int dp[N][N], n, m;
string s[N], t[N];
int lcs(const string &a, const string &b) {
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
dp[i + 1][j + 1] = max(dp[i + 1][j], dp[i][j + 1]);
if (a[i] == b[j]) {
dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);
}
}
}
return dp[n][m];
}
namespace LCS0SPOJ { //thx sk1
struct TBitset {
int sz, n;
unsigned a[N / 32 + 3];
TBitset() { n = 0; }
TBitset(int _n) {
memset(a, 0, sizeof(a));
sz = _n / 32 + 2; n = _n;
}
void Set(int x, int v) {
if(v == 1) {
a[x >> 5] |= 1U << (x & 31);
} else {
if((a[x >> 5] >> (x & 31)) & 1)
a[x >> 5] ^= 1U << (x & 31);
}
}
int Get(int x) {
return (a[x >> 5] >> (x & 31)) & 1;
}
TBitset operator | (const TBitset & b) {
TBitset r(n);
for(int i = 0; i < sz; ++i)
r.a[i] = a[i] | b.a[i];
return r;
}
TBitset operator & (const TBitset & b) {
TBitset r(n);
for(int i = 0; i < sz; ++i)
r.a[i] = a[i] & b.a[i];
return r;
}
TBitset operator ^ (const TBitset & b) {
TBitset r(n);
for(int i = 0; i < sz; ++i)
r.a[i] = a[i] ^ b.a[i];
return r;
}
void operator |= (const TBitset & b) {
for(int i = 0; i < sz; ++i)
a[i] |= b.a[i];
}
void operator &= (const TBitset & b) {
for(int i = 0; i < sz; ++i)
a[i] &= b.a[i];
}
void operator ^= (const TBitset & b) {
for(int i = 0; i < sz; ++i)
a[i] ^= b.a[i];
}
TBitset operator + (const TBitset & b) {
TBitset r(n);
bool ok = false;
for(int i = 0; i + 1 < sz; ++i) {
long long sum = (long long)a[i] + (long long)b.a[i] + ok;
r.a[i] = sum & ((1LL << 32) - 1);
ok = sum >> 32;
}
return r;
}
void operator += (const TBitset & b) {
memset(a, 0, sizeof(a));
for(int i = 0; i < sz; ++i) {
long long sum = (long long)a[i] + (long long)b.a[i];
a[i] += sum & ((1LL << 32) - 1);
a[i + 1] += sum >> 32;
}
}
TBitset operator ~ () {
TBitset r(n);
for(int i = 0; i < sz; ++i) {
r.a[i] = ~a[i];
}
return r;
}
void reset() {
memset(a, 0, sizeof(a));
}
} b, nb, nxb, eq[26], neq[26];
int lcs(const string &s, const string &t) {
int n = (int)s.length();
int m = (int)t.length();
b = TBitset(m + 1); nb = TBitset(m + 1);
for(int i = 0; i < 26; ++i) {
eq[i] = TBitset(m + 1);
neq[i] = TBitset(m + 1);
}
for(int i = 0; i < 26; ++i)
for(int j = 0; j < m; ++j) {
neq[i].Set(j, 1);
eq[i].Set(j, 0);
}
for(int i = 0; i < m; ++i) {
eq[t[i] - 'a'].Set(i, 1);
neq[t[i] - 'a'].Set(i, 0);
nb.Set(i, 1);
}
int ans = 0;
for(int i = 0; i < n; ++i) {
int dig = s[i] - 'a';
nxb = (nb + (nb & eq[dig])) | (nb & neq[dig]);
if(nxb.Get(m))
++ans;
for(int i = m; i < m + 32; ++i)
nxb.Set(m, 0);
nb = nxb;
}
return ans;
}
};
int main() {
// freopen("rowords.in", "r", stdin); freopen("rowords.out", "w", stdout);
string a, b;
getline(cin, a);
getline(cin, b);
swap(a, b);
n = a.length();
m = b.length();
int ans = 0;
for (int i = 0; i < n; ++i) {
s[i] = a.substr(i) + a.substr(0, i);
}
for (int i = 0; i < m; ++i) {
t[i] = b.substr(i) + b.substr(0, i);
}
for (int i = 0; i < 1; ++i) {
int curAns = 2;
for (int j = 0; j < m; ++j) {
if (ans <= curAns + 2) {
curAns = LCS0SPOJ::lcs(s[i], t[j]);
if (ans < curAns) {
ans = curAns;
}
}
curAns += 2;
}
for (int j = 0; j < m; ++j) {
reverse(t[j].begin(), t[j].end());
}
}
cout << ans << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
344 KB |
Output is correct |
| 5 |
Correct |
1 ms |
348 KB |
Output is correct |
| 6 |
Correct |
66 ms |
1848 KB |
Output is correct |
| 7 |
Correct |
255 ms |
3076 KB |
Output is correct |
| 8 |
Incorrect |
86 ms |
2908 KB |
Output isn't correct |
| 9 |
Correct |
112 ms |
3072 KB |
Output is correct |
| 10 |
Correct |
111 ms |
2908 KB |
Output is correct |
| 11 |
Correct |
179 ms |
3596 KB |
Output is correct |
| 12 |
Correct |
339 ms |
3672 KB |
Output is correct |
| 13 |
Correct |
117 ms |
3920 KB |
Output is correct |
| 14 |
Correct |
168 ms |
3420 KB |
Output is correct |
| 15 |
Correct |
203 ms |
3932 KB |
Output is correct |
| 16 |
Correct |
137 ms |
3332 KB |
Output is correct |
| 17 |
Incorrect |
245 ms |
3636 KB |
Output isn't correct |
| 18 |
Correct |
121 ms |
4188 KB |
Output is correct |
| 19 |
Correct |
130 ms |
2904 KB |
Output is correct |
| 20 |
Incorrect |
177 ms |
3756 KB |
Output isn't correct |
| 21 |
Correct |
183 ms |
4184 KB |
Output is correct |
| 22 |
Correct |
137 ms |
4744 KB |
Output is correct |
| 23 |
Correct |
180 ms |
4816 KB |
Output is correct |
| 24 |
Incorrect |
156 ms |
5212 KB |
Output isn't correct |
| 25 |
Incorrect |
141 ms |
5720 KB |
Output isn't correct |
