Submission #133362

#	Time	Username	Problem	Language	Result	Execution time	Memory
133362		IOrtroiii	Necklace (Subtask 4) (BOI19_necklace4)	C++14	15 / 15	451 ms	508 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

vector<int> eval(string s, string t) {
   int n = s.size();
   int m = t.size();
   vector<int> link(n);
   if (s.empty()) {
      return vector<int>(m, 0);
   }
   link[0] = -1;
   int cur = -1;
   for (int i = 1; i < n; ++i) {
      while (~cur && s[cur + 1] != s[i]) {
         cur = link[cur];
      }
      if (s[cur + 1] == s[i]) {
         cur++;
      }
      link[i] = cur;
   }
   cur = -1;
   vector<int> ans(m);
   for (int i = 0; i < m; ++i) {
      while (~cur && s[cur + 1] != t[i]) {
         cur = link[cur];
      }
      if (s[cur + 1] == t[i]) {
         cur++;
      }
      ans[i] = cur + 1;
   }
   return ans;
}

void debug(vector<int> a, string s) {
   cout << s << " ";
   for (int v : a) cout << v << " ";
   cout << "\n";
}

int main() {
   ios_base::sync_with_stdio(false);
   string s, t;
   cin >> s >> t;
   int n = s.size();
   int m = t.size();
   auto solve = [&]() {
      array<int, 3> ans = {0, 0, 0};
      for (int i = 0; i <= m; ++i) {
         string l, r;
         for (int j = 0; j < m; ++j) {
            if (j < i) {
               l += t[j];
            } else {
               r += t[j];
            }
         }
         reverse(l.begin(), l.end());
         reverse(s.begin(), s.end());
         auto gol = eval(l, s);
         reverse(gol.begin(), gol.end());
         reverse(s.begin(), s.end());
         auto gor = eval(r, s);
         // debug(gol, "gol is:");
         // debug(gor, "gor is:");
         for (int j = 0; j <= n; ++j) {
            int lenL = (j == 0 ? 0 : gor[j - 1]);
            int lenR = (j == n ? 0 : gol[j]);
            array<int, 3> cur = {lenL + lenR, j - lenL, i - lenR};
            ans = max(ans, cur);
         }
      }
      return ans;
   };
   auto l = solve();
   reverse(t.begin(), t.end());
   auto r = solve();
   cout << max(l[0], r[0]) << "\n";
   if (l[0] < r[0]) {
      cout << r[1] << " " << m - r[2] - r[0] << "\n";
   } else {
      cout << l[1] << " " << l[2] << "\n";
   }
}

• Subtask 1: 15 / 15