bool home = 1;
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;
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;
}
int max_possible_len = min(last + 1, (int) t.size() - first);
for (int len = max_possible_len; len >= 1; len--) {
if (longst[last - len + 1][first] >= len) {
return len;
}
}
return 0;
} else {
if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) {
return 0;
}
int max_possible_len = min(last + 1, (int) s.size() - first);
for (int len = max_possible_len; len >= 1; len--) {
if (longts[last - len + 1][first] >= len) {
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);
}
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, 0) + get_longest(last_b, first_b, 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, 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: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:138:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
138 | if (rev == 0) {
| ^~
necklace.cpp:141:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
141 | jump_b = (int) t.size() - (first_a + len_a);
| ~~~~~~~~~^~~~~~~~
necklace.cpp:132:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
132 | int jump_a = last_a - len_a + 1;
| ~~~~~~~^~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Expected integer, but "comps" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Expected integer, but "comps" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
212 KB |
Expected integer, but "comps" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
