bool home = 1;
bool verbose = 1;
#include <bits/stdc++.h>
using namespace std;
int comps = 0;
void compute(vector<vector<int>>& dp, vector<vector<int>> &dp2, 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;
}
}
dp2 = dp;
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;
}
}
}
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++;
}
dp2[last][first] = j;
if (j == dim) {
j = ps[j - 1];
}
}
}
}
vector<vector<int>> longst;
vector<vector<int>> longts;
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];
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) {
cout << " = " << len << " vs " << dpst[last][first] << "\n";
return len;
}
}
return 0;
} else {
if (!(0 <= last && last < (int) t.size() && 0 <= first && first < (int) s.size())) {
return 0;
}
return dpts[last][first];
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, dpst, s, t);
compute(longts, dpts, t, s);
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, dpst, s, t);
compute(longts, 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:111:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
111 | freopen ("___input___.txt", "r", stdin);
| ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
necklace.cpp:169:3: warning: 'r' may be used uninitialized in this function [-Wmaybe-uninitialized]
169 | if (rev == 0) {
| ^~
necklace.cpp:172:40: warning: 'f' may be used uninitialized in this function [-Wmaybe-uninitialized]
172 | jump_b = (int) t.size() - (first_a + len_a);
| ~~~~~~~~~^~~~~~~~
necklace.cpp:163:23: warning: 'l' may be used uninitialized in this function [-Wmaybe-uninitialized]
163 | int jump_a = last_a - len_a + 1;
| ~~~~~~~^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Expected integer, but "comps" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Expected integer, but "comps" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
1 ms |
212 KB |
Expected integer, but "comps" found |
| 2 |
Halted |
0 ms |
0 KB |
- |
