Submission #1073298

#	Time	Username	Problem	Language	Result	Execution time	Memory
1073298		duckindog	Necklace (Subtask 1-3) (BOI19_necklace1)	C++17	0 / 85	2 ms	348 KiB

necklace

#include <bits/stdc++.h>

using namespace std;

const int N = 3000 + 10;
string s, t;

struct Hash { 
  using ull = unsigned long long;
  static const int base = 19937;
  int n;
  vector<ull> pw, h, rh;
  Hash(string s) : n(s.size()), pw(s.size() + 1), h(s.size() + 1), rh(s.size() + 1) { 
    pw[0] = 1;
    for (int i = 1; i <= n; ++i) pw[i] = pw[i - 1] * base;
    for (int i = 1; i <= n; ++i) h[i] = h[i - 1] * base + s[i - 1];
    for (int i = 1; i <= n; ++i) rh[i] = rh[i - 1] * base + s[n - i];
  } 
  ull get(int l, int r) { return h[r] - h[l - 1] * pw[r - l + 1]; }
  ull rget(int l, int r) { 
    tie(l, r) = make_pair(n - r + 1, n - l + 1);
    return rh[r] - rh[l - 1] * pw[r - l + 1]; 
  }
};

int f[N][N];

int32_t main() { 
  cin.tie(0)->sync_with_stdio(0);

  cin >> s >> t;
  int n = s.size(), m = t.size();

  tuple<int, int, int> answer;

  for (int type = 0; type < 2; ++ type) {
    Hash S(s), T(t);
    for (int i = 1; i < n; ++i) { 
      for (int j = 1; j < m; ++j) { 
        int prefix = 0;
        { //calculate prefix
          for (int x = 0; x <= min(i, j) - 1; ++x) 
            if (S.get(i - x, i) == T.rget(j - x, j)) prefix = x + 1;
        }

        int suffix = 0;
        { //calculate suffix
          for (int x = 1; x <= min(n - i, m - j); ++x) 
            if (S.get(i + 1, i + x) == T.rget(j + 1, j + x)) suffix = x;
        }

        tuple<int, int, int> ret = {prefix + suffix, i - prefix, j - prefix};
        answer = max(answer, ret);
      }
    }
    reverse(t.begin(), t.end());
  }

  auto [lenght, i, j] = answer;
  cout << lenght << "\n";
  cout << i << " " << j << "\n";
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 20
• Subtask 3: 0 / 40