Submission #762574

#	Time	Username	Problem	Language	Result	Execution time	Memory
762574		qrno	Necklace (Subtask 4) (BOI19_necklace4)	C++17	0 / 15	1572 ms	340 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 < size(s); i++) {
    int j = pi[i-1];
    while (j && s[i] != s[j]) j = pi[j-1];
    while (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);

  array<int, 3> ans{0, 0, 0};
  string tr = t;
  reverse(begin(tr), end(tr));
  for (int i = 0; i < n; i++) {
    string s1 = s.substr(0, i), s2 = s.substr(i, n-(i+1));
    auto p1 = prefix_function(s2 + '$' + t);
    reverse(begin(s1), end(s1));
    auto p2 = prefix_function(s1 + '$' + tr);

    /* cout << s2 << '$' << t << endl; */
    /* for (auto x : p1) cout << x; */
    /* cout << endl; */
    /**/
    /* cout << s1 << '$' << tr << endl; */
    /* for (auto x : p2) cout << x; */
    /* cout << endl; */

    for (int j = 0; j < m; j++) {
      int blen = p1[size(s2)+1+j];
      int alen = p2[size(p2)-1-j-1];
      if (alen + blen > ans[0]) {
        ans[0] = alen + blen;
        ans[1] = i - alen + 1;
        ans[2] = j - blen + 1;

        if (!rev) ans[2] = m - 1 - j;
      }
    }
  }
  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] << endl;
}

Compilation message (stderr)

necklace.cpp: In function 'std::vector<int> prefix_function(const string&)':
necklace.cpp:8:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |   for (int i = 1; i < size(s); i++) {
      |                   ~~^~~~~~~~~

• Subtask 1: 0 / 15