# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
645950 | alextodoran | Necklace (Subtask 4) (BOI19_necklace4) | C++17 | 598 ms | 476 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
/**
____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|
**/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int L_MAX = 3000;
string a, b;
int n, m;
int kmpPrefA[L_MAX + 2];
int kmpSuffA[L_MAX + 2];
int kmpPrefB[L_MAX + 2];
int kmpSuffB[L_MAX + 2];
vector <int> solve () {
vector <int> best = {0, 0, 0};
for (int i = 0; i < n; i++) {
kmpPrefA[i] = 0;
for (int j = i + 1; j < n; j++) {
kmpPrefA[j] = kmpPrefA[j - 1];
while (kmpPrefA[j] > 0 && a[i + kmpPrefA[j]] != a[j]) {
kmpPrefA[j] = kmpPrefA[i + kmpPrefA[j] - 1];
}
if (a[i + kmpPrefA[j]] == a[j]) {
kmpPrefA[j]++;
}
}
kmpPrefB[0] = (a[i] == b[0] ? 1 : 0);
for (int j = 1; j < m; j++) {
kmpPrefB[j] = kmpPrefB[j - 1];
while (kmpPrefB[j] > 0 && a[i + kmpPrefB[j]] != b[j]) {
kmpPrefB[j] = kmpPrefA[i + kmpPrefB[j] - 1];
}
if (a[i + kmpPrefB[j]] == b[j]) {
kmpPrefB[j]++;
}
}
if (i > 0) {
kmpSuffA[i - 1] = 0;
for (int j = i - 2; j >= 0; j--) {
kmpSuffA[j] = kmpSuffA[j + 1];
while (kmpSuffA[j] > 0 && a[(i - 1) - kmpSuffA[j]] != a[j]) {
kmpSuffA[j] = kmpSuffA[(i - 1) - kmpSuffA[j] + 1];
}
if (a[(i - 1) - kmpSuffA[j]] == a[j]) {
kmpSuffA[j]++;
}
}
kmpSuffB[m - 1] = (a[i - 1] == b[m - 1] ? 1 : 0);
for (int j = m - 2; j >= 0; j--) {
kmpSuffB[j] = kmpSuffB[j + 1];
while (kmpSuffB[j] > 0 && a[(i - 1) - kmpSuffB[j]] != b[j]) {
kmpSuffB[j] = kmpSuffA[(i - 1) - kmpSuffB[j] + 1];
}
if (a[(i - 1) - kmpSuffB[j]] == b[j]) {
kmpSuffB[j]++;
}
}
}
for (int j = 0; j < m; j++) {
int x = kmpPrefB[j];
int y = 0;
if (0 < i && j < m - 1) {
y = kmpSuffB[j + 1];
}
vector <int> here = {x + y, i - y, j - x + 1};
if (here[0] > best[0]) {
best = here;
}
}
}
return best;
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> a >> b;
n = (int) a.size(); m = (int) b.size();
vector <int> best1 = solve();
reverse(b.begin(), b.end());
vector <int> best2 = solve();
best2[2] = m - best2[2] - best2[0];
if (best1[0] < best2[0]) {
swap(best1, best2);
}
cout << best1[0] << "\n";
cout << best1[1] << " " << best1[2] << "\n";
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |