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 (int i = n - 1; i >= 0; i--) {
for (int j = m - 1; j >= 0; j--) {
if (s[i] == t[j]) {
dp[i][j] = 1;
if (i + 1 < n && j + 1 < m) {
dp[i][j] += dp[i + 1][j + 1];
}
} else {
dp[i][j] = 0;
}
}
}
}
vector<vector<int>> longst;
vector<vector<int>> longts;
int get_longest(int last, int first, string& s, string& t, bool cs) {
string rev_t = t;
reverse(rev_t.begin(), rev_t.end());
int n = (int) s.size(), m = (int) t.size();
if (!(0 <= last && last < n && 0 <= first && first < m)) {
return 0;
}
int max_possible_len = min(last + 1, m - first);
for (int len = max_possible_len; len >= 1; len--) {
bool ok = 1;
for (int i = 0; i < len; i++) {
assert(0 <= first + i && first + i < (int) t.size());
assert(0 <= last - len + 1 + i && last - len + 1 + i < (int) s.size());
assert(t[first + i] == rev_t[(int) t.size() - 1 - first - i]);
comps++;
ok &= (s[last - len + 1 + i] == t[first + i]);
}
if (cs == 0) {
assert(ok == (longst[last - len + 1][first] >= len));
} else {
assert(ok == (longts[last - len + 1][first] >= len));
}
if (ok) {
return len;
}
}
return 0;
}
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);
}
string s, t;
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();
longst.clear();
longts.clear();
longst.resize(n, vector<int> (m));
longts.resize(m, vector<int> (n));
compute(longst, s, t);
compute(longts, t, s);
/**
AB
BA
**/
for (int last_a = 0; last_a < n; last_a++) {
for (int first_a = 0; first_a < m; first_a++) {
int first_b = last_a + 1;
int last_b = first_a - 1;
int cur = get_longest(last_a, first_a, s, t, 0) + get_longest(last_b, first_b, t, s, 1);
if (cur > sol) {
sol = cur;
l = last_a;
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();
longst.clear();
longts.clear();
longst.resize(n, vector<int> (m));
longts.resize(m, vector<int> (n));
compute(longst, s, t);
compute(longts, 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, s, t, 0);
int len_b = get_longest(last_b, first_b, t, s, 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:73:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
73 | freopen ("___input___.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:139:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
139 | if (rev == 0) {
| ^~
necklace.cpp:142:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
142 | jump_b = (int) t.size() - (first_a + len_a);
| ~~~~~~~~~^~~~~~~~
necklace.cpp:133:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
133 | int jump_a = last_a - len_a + 1;
| ~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
400 KB |
Output is correct |
| 2 |
Correct |
53 ms |
340 KB |
Output is correct |
| 3 |
Correct |
51 ms |
372 KB |
Output is correct |
| 4 |
Correct |
59 ms |
380 KB |
Output is correct |
| 5 |
Correct |
85 ms |
376 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
400 KB |
Output is correct |
| 2 |
Correct |
53 ms |
340 KB |
Output is correct |
| 3 |
Correct |
51 ms |
372 KB |
Output is correct |
| 4 |
Correct |
59 ms |
380 KB |
Output is correct |
| 5 |
Correct |
85 ms |
376 KB |
Output is correct |
| 6 |
Execution timed out |
1592 ms |
1492 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
50 ms |
400 KB |
Output is correct |
| 2 |
Correct |
53 ms |
340 KB |
Output is correct |
| 3 |
Correct |
51 ms |
372 KB |
Output is correct |
| 4 |
Correct |
59 ms |
380 KB |
Output is correct |
| 5 |
Correct |
85 ms |
376 KB |
Output is correct |
| 6 |
Execution timed out |
1592 ms |
1492 KB |
Time limit exceeded |
| 7 |
Halted |
0 ms |
0 KB |
- |
