Submission #762637

#	Time	Username	Problem	Language	Result	Execution time	Memory
762637		qrno	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	314 ms	528 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(string const& s) {
  int n = size(s);
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i-1];
    while (j && s[i] != s[j]) j = pi[j-1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
  return pi;
}

array<int, 3> solve(string const& s, string const& t, bool rev) {
  int n = size(s), m = size(t);

  string tr = t;
  reverse(begin(tr), end(tr));

  array<int, 3> ans{0, 0, 0};
  for (int i = 0; i < n; i++) {
    string s1 = s.substr(0, i), s2 = s.substr(i, n-i);
    reverse(begin(s1), end(s1));

    auto p1 = prefix_function(s1 + '$' + t);
    auto p2 = prefix_function(s2 + '$' + tr);

    for (int j = 1; j <= m; j++) {
      array<int, 3> a = {p1[i+j] + p2[n+m-i-j],
                         i - p1[i+j],
                         rev ? m - j - p2[n+m-i-j] : j - p1[i+j]};
      ans = max(ans, a);
    }
  }
  return ans;
}

int main() {
  string s, t;
  cin >> s >> t;

  auto ans = solve(s, t, false);
  reverse(begin(t), end(t));
  ans = max(ans, solve(s, t, true));
  cout << ans[0] << '\n' << ans[1] << ' ' << ans[2] << '\n';
}

• Subtask 1: 15 / 15