Submission #557678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
557678	2022-05-05T18:34:33 Z	Soumya1	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	447 ms	588 KB

necklace

#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 - 1];
    if (s[j] == s[i]) j++;
    pi[i] = j;
  }
  return pi;
}
vector<int> suffix_function(string s) { // :P there is no such thing. I just named it (actually same as prefix function)
  int n = s.size();
  vector<int> pi(n);
  pi[n - 1] = n - 1;
  for (int i = n - 2; i >= 0; i--) {
    int j = pi[i + 1];
    while (j < n - 1 && s[j] != s[i]) j = pi[j + 1];
    if (s[j] == s[i]) j--;
    pi[i] = j;
  }
  for (int &i : pi) {
    i = n - 1 - i;
  }
  return pi;
}
tuple<int, int, int> solve(string s, string t, bool f = false) {
  int n = s.size(), m = t.size();
  tuple<int, int, int> ret = {0, 0, 0};
  for (int i = 0; i < n; i++) {
    string s1 = s.substr(0, i);
    string s2 = s.substr(i, n - i);
    string ss1 = s2 + '#' + t;
    string ss2 = t + '#' + s1;
    auto pi = prefix_function(ss1);
    auto si = suffix_function(ss2);
    int a[m], b[m];
    memset(a, 0, sizeof a);
    memset(b, 0, sizeof b);
    for (int j = 0; j < m; j++) {
      a[j] = pi[j + n - i + 1];
      b[j] = si[j];
    }
    for (int j = 0; j < m; j++) {
      ret = max(ret, {a[j], i, j - a[j] + 1});
      ret = max(ret, {b[j], i - b[j], j});
      if (j >= 1) {
        ret = max(ret, {a[j - 1] + b[j], i - b[j], j - a[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;
}

Subtask #1

15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	429 ms	464 KB	Output is correct
2	Correct	397 ms	544 KB	Output is correct
3	Correct	447 ms	548 KB	Output is correct
4	Correct	352 ms	588 KB	Output is correct
5	Correct	335 ms	432 KB	Output is correct
6	Correct	350 ms	480 KB	Output is correct
7	Correct	378 ms	472 KB	Output is correct
8	Correct	390 ms	476 KB	Output is correct
9	Correct	407 ms	432 KB	Output is correct