#include<cstdio>
#include<algorithm>
using namespace std;
char p[4010], q[2010];
int n, m, D[4010][2010];
int dir[4010][2010], res;
bool OK[4010][2010];
void Do() {
int i, j;
for (i = 1; i <= n; i++)p[i + n] = p[i];
for (i = 0; i <= n + n; i++) {
for (j = 0; j <= m; j++) {
dir[i][j] = D[i][j] = 0;
if (i&&j) {
if (p[i] == q[j])OK[i][j] = true;
else OK[i][j] = false;
}
}
}
for (i = 0; i <= n; i++) {
for (j = 0; j <= m; j++) {
if (i == 0 && j == 0)continue;
if (i == 0) continue;
if (j == 0) {
dir[i][j] = 2;
continue;
}
D[i][j] = D[i][j - 1];
if (OK[i][j] && D[i][j] < D[i - 1][j - 1] + 1) {
D[i][j] = D[i - 1][j - 1] + 1, dir[i][j] = 1;
}
if (D[i][j] < D[i - 1][j]) {
D[i][j] = D[i - 1][j], dir[i][j] = 2;
}
}
}
for (i = 1; i <= n; i++) {
for (j = 1; j <= m; j++) {
if (dir[i][j]) {
break;
}
}
if (j != m + 1) {
int x = i, y = j;
dir[x][y] = 0;
while (x < i + n - 1 && y <= m) {
if (dir[x + 1][y] == 2) {
x++;
dir[x][y] = 0;
}
else if (dir[x + 1][y + 1] == 1) {
x++, y++;
dir[x][y] = 0;
}
else y++;
}
if (y <= m) {
for (j = y; j <= m; j++)D[i + n - 1][j]--;
}
}
for (j = 0; j <= m; j++) {
if (j == 0) {
dir[i + n][j] = 2;
D[i + n][j] = D[i + n - 1][j];
continue;
}
D[i + n][j] = D[i + n][j - 1];
if (OK[i + n][j] && D[i + n][j] < D[i + n - 1][j - 1] + 1)D[i + n][j] = D[i + n - 1][j - 1] + 1, dir[i + n][j] = 1;
if (D[i + n][j] < D[i + n - 1][j])D[i + n][j] = D[i + n - 1][j], dir[i + n][j] = 2;
}
res = max(res, D[i + n][m]);
}
}
int main() {
scanf("%s%s", p + 1, q + 1);
int i;
for (i = 1; p[i]; i++);
n = i - 1;
for (i = 1; q[i]; i++);
m = i - 1;
Do();
reverse(p + 1, p + n + 1);
Do();
printf("%d\n", res);
}
Compilation message
rowords.cpp: In function 'int main()':
rowords.cpp:75:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%s%s", p + 1, q + 1);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
504 KB |
Output is correct |
| 2 |
Correct |
2 ms |
504 KB |
Output is correct |
| 3 |
Correct |
2 ms |
760 KB |
Output is correct |
| 4 |
Correct |
3 ms |
1272 KB |
Output is correct |
| 5 |
Correct |
3 ms |
1244 KB |
Output is correct |
| 6 |
Correct |
26 ms |
21880 KB |
Output is correct |
| 7 |
Correct |
51 ms |
35704 KB |
Output is correct |
| 8 |
Correct |
104 ms |
35704 KB |
Output is correct |
| 9 |
Correct |
97 ms |
35704 KB |
Output is correct |
| 10 |
Correct |
85 ms |
35704 KB |
Output is correct |
| 11 |
Correct |
88 ms |
39288 KB |
Output is correct |
| 12 |
Correct |
82 ms |
42972 KB |
Output is correct |
| 13 |
Correct |
119 ms |
42856 KB |
Output is correct |
| 14 |
Correct |
97 ms |
40696 KB |
Output is correct |
| 15 |
Correct |
105 ms |
44024 KB |
Output is correct |
| 16 |
Correct |
116 ms |
38552 KB |
Output is correct |
| 17 |
Correct |
84 ms |
42360 KB |
Output is correct |
| 18 |
Correct |
112 ms |
50680 KB |
Output is correct |
| 19 |
Correct |
78 ms |
35704 KB |
Output is correct |
| 20 |
Correct |
126 ms |
45408 KB |
Output is correct |
| 21 |
Correct |
53 ms |
38264 KB |
Output is correct |
| 22 |
Correct |
74 ms |
43256 KB |
Output is correct |
| 23 |
Correct |
80 ms |
46088 KB |
Output is correct |
| 24 |
Correct |
84 ms |
48668 KB |
Output is correct |
| 25 |
Correct |
102 ms |
54380 KB |
Output is correct |
