# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
754806 | adaawf | Necklace (Subtask 4) (BOI19_necklace4) | C++14 | 329 ms | 524 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.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> kmp(string s) {
int n = s.size();
vector<int> k(n);
for (int i = 1; i < n; i++) {
int j = k[i - 1];
while (j != 0 && s[i] != s[j]) {
j = k[j - 1];
}
if (s[i] == s[j]) {
j++;
}
k[i] = j;
}
return k;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
string s, t;
cin >> s >> t;
int n = s.size(), m = t.size(), ma = 0;
pair<int, int> p;
for (int i = 0; i < n; i++) {
string h = s.substr(0, i), k = s.substr(i, n - i), g = t;
reverse(h.begin(), h.end());
reverse(g.begin(), g.end());
vector<int> v = kmp(h + '#' + t), vv = kmp(k + '#' + g);
for (int j = 1; j <= m; j++) {
int h = v[i + j] + vv[n + m - i - j];
if (ma < h) {
ma = h;
p = {i - v[i + j], j - v[i + j]};
}
}
}
reverse(t.begin(), t.end());
for (int i = 0; i < n; i++) {
string h = s.substr(0, i), k = s.substr(i, n - i), g = t;
reverse(h.begin(), h.end());
reverse(g.begin(), g.end());
vector<int> v = kmp(h + '#' + t), vv = kmp(k + '#' + g);
for (int j = 1; j <= m; j++) {
int h = v[i + j] + vv[n + m - i - j];
if (ma < h) {
ma = h;
p = {i - v[i + j], m - j - vv[n + m - i - j]};
}
}
}
cout << ma << endl;
cout << p.first << ' ' << p.second;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |