Submission #1165535

#	Time	Username	Problem	Language	Result	Execution time	Memory
1165535		luishgh	Necklace (Subtask 4) (BOI19_necklace4)	C++20	0 / 15	144 ms	568 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

#define _ ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'

typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

const int MAX = 2*(3e3 + 10);

void kmp(const string& s, vector<int>& pi) {
  pi.resize(s.size());
  pi[0] = 0;
  int j = 0;
  for (int i = 1; i < s.size(); i++) {
    while (j > 0 and s[i] != s[j])
      j = pi[j-1];
    if (s[i] == s[j]) j++;
    pi[i] = j;
  }
}

int main() {_;

  string s, t; cin >> s >> t;
  reverse(begin(t), end(t));

  int ans = 0;
  int sta = 0, stb = 0;
  for (int i = 0; i < s.size(); i++) {
    vector<int> p0, p1;
    auto s1 = s.substr(0, i); auto s2 = s.substr(i);
    auto t1 = t; auto t2 = t;
    reverse(begin(s1), end(s1));
    reverse(begin(t2), end(t2));
    kmp(s1 + "$" + t1, p0);
    kmp(s2 + "$" + t2, p1);
    for (int j = 1; j <= t.size(); j++) {
      int sc = p0[i + j] +
        p1[s2.size()+ t.size() - j];
      if (sc > ans) {
        ans = sc;
        sta = i+1 - p0[i+j];
        stb = t.size() - j - p1[s2.size() + t.size() - j];
      }
    }
  }

  reverse(begin(s), end(s));

  for (int i = 0; i < s.size(); i++) {
    vector<int> p0, p1;
    auto s1 = s.substr(0, i); auto s2 = s.substr(i);
    auto t1 = t; auto t2 = t;
    reverse(begin(s1), end(s1));
    reverse(begin(t2), end(t2));
    kmp(s1 + "$" + t1, p0);
    kmp(s2 + "$" + t2, p1);
    for (int j = 1; j <= t.size(); j++) {
      int sc = p0[i + j] +
        p1[s2.size()+ t.size() - j];
      if (sc > ans) {
        ans = sc;
        sta = s.size() - i - p0[i+j];
        stb = t.size() - j - p1[s2.size() + t.size() - j];
      }
    }
  }

  cout << ans << endl;
  cout << sta << ' ' << stb << endl;

  return 0;
}

• Subtask 1: 0 / 15