Submission #584886

#	Time	Username	Problem	Language	Result	Execution time	Memory
584886		slime	Necklace (Subtask 1-3) (BOI19_necklace1)	C++14	17 / 85	120 ms	472 KiB

necklace

#include "bits/stdc++.h"
using namespace std;
#define int long long
const int MAXN = 3004;
const int MOD = 998244353;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
vector<int> prefix_function(string t) {
  int n = t.size();
  vector<int> lps(n);
  lps[0] = 0;
  for(int i=1; i<n; i++) {
    int j = lps[i-1];
    while(j > 0 && t[i] != t[j]) {
      j = lps[j-1];
    }
    if(t[i] == t[j]) lps[i] = j+1;
    else lps[i] = 0;
  }
  return lps;
}
int ans1, sst, tst;
int pows[6010];
int aa[6010], bb[6010];
const int factor = 2017;
int hasha(int l, int r) {
  int qq = aa[l-1] * pows[r - l + 1];
  qq %= MOD;
  int given = aa[r] - qq; 
  if(given < 0) given = (MOD - (abs(given) % MOD)) % MOD;
  else given %= MOD;
  return given;
}
int hashb(int l, int r) {
  int qq = bb[l-1] * pows[r - l + 1];
  qq %= MOD;
  int given = bb[r] - qq; 
  if(given < 0) given = (MOD - (abs(given) % MOD)) % MOD;
  else given %= MOD;
  return given;
}
pair<int, pair<int, int> > lcs(string a, string b) { // length, starting positions
  int n = a.size(), m = b.size();
  a = " " + a;
  b = " " + b;
  int dp[2][m+1];
  for(int i=0; i<2; i++) for(int j=0; j<=m; j++) dp[i][j] = 0;
  int ma = 0;
  for(int i=1; i<=n; i++) {
    for(int j=0; j<=m; j++) dp[i & 1][j] = 0;
    for(int j=1; j<=m; j++) {
      if(a[i] == b[j]) dp[i & 1][j] = dp[(i-1) & 1][j-1] + 1;
      else dp[i & 1][j] = 0;
      ma = max(ma, dp[i & 1][j]);
    }
  }
  aa[0] = bb[0] = 0;
  for(int i=1; i<=n; i++) aa[i] = (aa[i-1] * factor + a[i]) % MOD;
  for(int i=1; i<=m; i++) bb[i] = (bb[i-1] * factor + b[i]) % MOD;
  for(int i=1; i<=n-ma+1; i++) {
    for(int j=1; j<=m-ma+1; j++) {
      if(hasha(i, i+ma-1) == hashb(j, j+ma-1)) {
        return {ma, {i, j} };
      }
    }
  }
  assert(false);
}
void upd_ans(int new_len, int new_sst, int new_tst) {
  if(new_len > ans1) {
    ans1 = new_len;
    sst = new_sst;
    tst = new_tst;
  }
}
void out() {
  cout << ans1 << "\n";
  cout << sst - 1 << " " << tst - 1 << "\n";
}
void solve(int tc) {
  pows[0] = 1;
  for(int i=1; i<6010; i++) pows[i] = (pows[i-1] * factor) % MOD;
  string s, t;
  cin >> s >> t;
  // Need to compute answer for both t and rev(t), both s and rev(s), for all suffixes of s and t
  // Can't be more duliu

  /*
  for(int i=0; i<s.size(); i++) {
    string u;
    u += s.substr(i, s.size() - i);
    u += "?";
    u += t; // ~ 6000
    vector<int> lps = prefix_function(u);
    bool 

  }

  */

  // Compute lcs of s and t
  pair<int, pair<int, int> > res = lcs(s, t);
  upd_ans(res.first, res.second.first, res.second.second);
  // Compute lcs of s and rev(t)
  reverse(t.begin(), t.end());
  res = lcs(s, t);
  upd_ans(res.first, res.second.first, (int) t.size() - res.second.second - res.first + 2);

  reverse(t.begin(), t.end());
  out();
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
// I don't know geometry.
// Teaming is unfair.

• Subtask 1: 5 / 25
• Subtask 2: 4 / 20
• Subtask 3: 8 / 40