Submission #651120

#	Time	Username	Problem	Language	Result	Execution time	Memory
651120		lto5	Necklace (Subtask 4) (BOI19_necklace4)	C++14	0 / 15	473 ms	35736 KiB

necklace

#include <bits/stdc++.h>
using namespace std;

const int N = 3005;

short f[N][N], g[N][N];
int pi[2*N];
int ans;
int start_a = -1;
int start_b = -1;

void solve (string s, string t, bool reversed = false) {
  int n = s.size();
  int m = t.size();

  s = ' ' + s;
  t = ' ' + t;
  string cur = "";

  auto reset = [&]() {
    int lim = n + m + 5;
    for (int i = 0; i <= lim; i++)
      pi[i] = 0;
  };

  auto add = [&] (int i) -> int {
    int j = pi[i - 1];
    while (j > 0 && cur[j] != cur[i]) {
      j = pi[j - 1];
    }
    if (cur[i] == cur[j])
      pi[i] = j + 1;

    return pi[i];
  };

  for (int cut_b = 1; cut_b <= m; cut_b++) {
    reset();
    cur = t.substr(cut_b);
    cur = cur + '.';

    for (int i = 1; i < cur.size(); i++) {
      add(i);
    }

    for (int cut_a = 1; cut_a <= n; cut_a++) {
      cur.push_back(s[cut_a]);
      f[cut_a][cut_b] = add((int)cur.size() - 1);
    }
  }

  for (int cut_a = 1; cut_a <= n; cut_a++) {
    reset();
    cur = s.substr(cut_a);
    cur = cur + '.';

    for (int i = 1; i < cur.size(); i++) {
      add(i);
    }

    for (int cut_b = 1; cut_b <= m; cut_b++) {
      cur.push_back(t[cut_b]);
      g[cut_a][cut_b] = add((int)cur.size() - 1);
    }
  }

  for (int cut_a = 1; cut_a <= n; cut_a++)
    for (int cut_b = 1; cut_b <= m; cut_b++) {
      int cur = f[cut_a][cut_b] + g[cut_a + 1][cut_b - 1];
      if (ans < cur) {
        ans = cur;
        start_a = cut_a - f[cut_a][cut_b] + 1;
        start_b = cut_b - 1 - g[cut_a + 1][cut_b - 1] + 1;
        if (reversed) {
          start_b += cur - 1;
          start_b = m - start_b + 1;
        }
      }
    }
}

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);

  string s, t;
  cin >> s >> t;

  solve(s, t);
  reverse(t.begin(), t.end());
  solve(s, t, 1);

  cout << ans << "\n";
  cout << start_a-1 << " " << start_b-1;

  return 0;
}

Compilation message (stderr)

necklace.cpp: In function 'void solve(std::string, std::string, bool)':
necklace.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     for (int i = 1; i < cur.size(); i++) {
      |                     ~~^~~~~~~~~~~~
necklace.cpp:57:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for (int i = 1; i < cur.size(); i++) {
      |                     ~~^~~~~~~~~~~~

• Subtask 1: 0 / 15