답안 #557657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
557657 2022-05-05T17:51:27 Z Soumya1 Necklace (Subtask 4) (BOI19_necklace4) C++17
0 / 15
32 ms 65536 KB
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
vector<int> prefix_function(string &s) {
  int n = s.size();
  vector<int> pi(n);
  for (int i = 1; i < n; i++) {
    int j = pi[i - 1];
    while (j > 0 && s[j] != s[i]) j = pi[j];
    if (s[j] == s[i]) j++;
    pi[i] = j;
  }
  return pi;
}
tuple<int, int, int> solve(string s, string t, bool f = false) {
  int n = s.size(), m = t.size();
  int a[n][m], b[n][m];
  memset(a, 0, sizeof a);
  memset(b, 0, sizeof b);
  auto _s = s;
  for (int i = 0; i < n; i++) {
    string ss = s + '#' + t;
    auto pi = prefix_function(ss);
    for (int j = 0; j < m; j++) {
      a[i][j] = pi[j + n - i + 1];
    }
    s.erase(s.begin());
  }
  s = _s;
  for (int j = 0; j < m; j++) {
    string ss = t + '#' + s;
    auto pi = prefix_function(ss);
    for (int i = 0; i < n; i++) {
      b[i][j] = pi[i + m - j + 1];
    }
    t.erase(t.begin());
  }
  tuple<int, int, int> ret = {0, 0, 0};
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      ret = max(ret, {a[i][j], i, j - a[i][j] + 1});
      ret = max(ret, {b[i][j], i - b[i][j] + 1, j});
      if (i - 1 >= 0 && j + 1 < m) {
        ret = max(ret, {a[i][j] + b[i - 1][j + 1], i - 1 - b[i - 1][j + 1] + 1, j  - a[i][j] + 1});
      }
    }
  }
  if (f) {
    auto &[l, i, j] = ret;
    i = n - i - l;
  }
  return ret;
}
void testCase() {
  string s, t;
  cin >> s >> t;
  auto a = solve(s, t);
  reverse(s.begin(), s.end());
  auto b = solve(s, t, true);
  a = max(a, b);
  auto [l, i, j] = a;
  cout << l << "\n";
  cout << i << " " << j << "\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  testCase();
  return 0;
}
# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 65536 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -