bool home = 0;
bool verbose = 1;
#include <bits/stdc++.h>
using namespace std;
int comps = 0;
void compute(vector<vector<int>>& dp,string &s, string &t) {
int n = (int) s.size();
int m = (int) t.size();
assert((int) dp.size() == n);
for (int i = 0; i < n; i++) {
assert((int) dp[i].size() == m);
}
for (auto &v : dp) {
for (auto &x : v) {
x = 0;
}
}
for (int first = 0; first < m; first++) {
string guy(t.begin() + first, t.end());
int dim = (int) guy.size();
vector<int> ps(dim, 0);
int j = 0;
for (int i = 1; i < dim; i++) {
while (j && guy[i] != guy[j]) {
j = ps[j - 1];
}
if (guy[i] == guy[j]) {
j++;
}
ps[i] = j;
}
j = 0;
for (int last = 0; last < n; last++) {
while (j && s[last] != guy[j]) {
j = ps[j - 1];
}
if (s[last] == guy[j]) {
j++;
}
dp[last][first] = j;
if (j == dim) {
j = ps[j - 1];
}
}
}
}
vector<vector<int>> dpst;
vector<vector<int>> dpts;
string s;
string t;
int get_longest(int last, int first, bool cs) {
if (cs == 0) {
if (!(0 <= last && last < (int) s.size() && 0 <= first && first < (int) t.size())) {
return 0;
}
return dpst[last][first];
} else {
if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) {
return 0;
}
return dpts[last][first];
}
}
int main() {
if (!home) {
verbose = 0;
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
}
if (home) {
verbose = 1;
freopen ("___input___.txt", "r", stdin);
}
cin >> s >> t;
int sol = -1, l, f, r;
for (int rev_t = 0; rev_t <= 1; rev_t++) {
int n = (int) s.size(), m = (int) t.size();
dpst.resize(n, vector<int> (m));
dpts.resize(m, vector<int> (n));
compute(dpst, s, t);
compute(dpts, t, s);
for (int last_a = 0; last_a <= n - 2; last_a++) {
{
int cur = dpst[last_a][0];
if (cur > sol) {
sol = cur;
l = last_a;
f = 0;
r = rev_t;
}
}
for (int first_a = 1; first_a < m; first_a++) {
int cur = dpst[last_a][first_a] + dpts[first_a - 1][last_a + 1];
if (cur > sol) {
sol = cur;
l = last_a;
f = first_a;
r = rev_t;
}
}
}
{
for (int first_a = 0; first_a < m; first_a++) {
int cur = dpst[n - 1][first_a];
if (cur > sol) {
sol = cur;
l = n - 1;
f = first_a;
r = rev_t;
}
}
}
reverse(t.begin(), t.end());
}
if (r) {
reverse(t.begin(), t.end());
}
int n = (int) s.size(), m = (int) t.size();
dpst.resize(n, vector<int> (m));
dpts.resize(m, vector<int> (n));
compute(dpst, s, t);
compute(dpts, t, s);
int rev = r;
int last_a = l;
int first_a = f;
int first_b = last_a + 1;
int last_b = first_a - 1;
int len_a = get_longest(last_a, first_a, 0);
int len_b = get_longest(last_b, first_b, 1);
/// [last_a - len_a]
/// [last_b - len_b]
int jump_a = last_a - len_a + 1;
int jump_b;
/// [a, b]
/// [b, a]
if (rev == 0) {
jump_b = last_b - len_b + 1;
} else {
jump_b = (int) t.size() - (first_a + len_a);
}
if (verbose) {
cout << "\t\t\t\t\tcomps = " << comps << "\n";
}
cout << sol << "\n";
cout << jump_a << " " << jump_b << "\n";
return 0;
}
Compilation message
necklace.cpp: In function 'int main()':
necklace.cpp:81:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
81 | freopen ("___input___.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:153:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
153 | if (rev == 0) {
| ^~
necklace.cpp:156:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
156 | jump_b = (int) t.size() - (first_a + len_a);
| ~~~~~~~~~^~~~~~~~
necklace.cpp:147:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
147 | int jump_a = last_a - len_a + 1;
| ~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1620 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1412 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1564 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
340 KB |
Output is correct |
| 2 |
Correct |
1 ms |
340 KB |
Output is correct |
| 3 |
Correct |
1 ms |
340 KB |
Output is correct |
| 4 |
Correct |
1 ms |
340 KB |
Output is correct |
| 5 |
Correct |
1 ms |
340 KB |
Output is correct |
| 6 |
Correct |
7 ms |
1620 KB |
Output is correct |
| 7 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 8 |
Correct |
6 ms |
1412 KB |
Output is correct |
| 9 |
Correct |
6 ms |
1564 KB |
Output is correct |
| 10 |
Correct |
6 ms |
1620 KB |
Output is correct |
| 11 |
Correct |
5 ms |
1492 KB |
Output is correct |
| 12 |
Correct |
5 ms |
1492 KB |
Output is correct |
| 13 |
Correct |
775 ms |
71032 KB |
Output is correct |
| 14 |
Correct |
721 ms |
71036 KB |
Output is correct |
| 15 |
Correct |
718 ms |
66880 KB |
Output is correct |
| 16 |
Correct |
700 ms |
69868 KB |
Output is correct |
| 17 |
Correct |
658 ms |
68468 KB |
Output is correct |
| 18 |
Correct |
663 ms |
70500 KB |
Output is correct |
| 19 |
Correct |
656 ms |
70448 KB |
Output is correct |
| 20 |
Correct |
683 ms |
68508 KB |
Output is correct |
| 21 |
Correct |
711 ms |
69284 KB |
Output is correct |
