제출 #823944

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
823944		tch1cherin	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	350 ms	440 KiB

necklace

#include <bits/stdc++.h>
using namespace std;
 
vector<int> prefix_function(string s) {
  int n = (int)s.size();
  vector<int> pi(n);
  for (int i = 1; i < n; ++i) {
    int j = pi[i - 1];
    while (j > 0 && s[i] != s[j]) {
      j = pi[j - 1];
    }
    if (s[i] == s[j]) {
      ++j;
    }
    pi[i] = j;
  }
  return pi;
}
 
int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  string A, B;
  cin >> A >> B;
  tuple<int, int, int> ans = {0, 0, 0};
  for (int r = 0; r < 2; r++) {
    string S = A + "#" + B, T = B + "#" + A;
    for (int i = 0; i < (int)A.size(); i++) {
      vector<int> sPi = prefix_function(S.substr(i, S.size() - i));
      reverse(sPi.begin(), sPi.end());
      for (int j = 0; j < i; j++) {
        sPi.push_back(0);
      }
      reverse(sPi.begin(), sPi.end());
      string tt = T;
      tt = tt.substr(0, B.size() + i + 1);
      reverse(tt.begin(), tt.end());
      vector<int> tPi = prefix_function(tt);
      reverse(tPi.begin(), tPi.end());
      for (int j = 0; j < (int)B.size(); j++) {
        int rightleft = sPi[A.size() + j];
        int leftright = tPi[j];
        int res = rightleft + leftright, x = i - leftright, y = j - rightleft;
        if (r == 1) {
          y = (int)B.size() - res - y;
        }
        ans = max(ans, {res, x, y});
      }
    }
    reverse(B.begin(), B.end());
  }
  cout << get<0>(ans) << "\n" << get<1>(ans) << " " << get<2>(ans) << "\n";
}

• Subtask 1: 15 / 15