Submission #678489

#	Time	Username	Problem	Language	Result	Execution time	Memory
678489		cig32	Necklace (Subtask 4) (BOI19_necklace4)	C++17	15 / 15	517 ms	668 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";
}
string reversed(string x) {
  reverse(x.begin(), x.end());
  return x;
}
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;
  int n = s.size(), m = t.size();
  s = " " + s;
  t = " " + 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=2; i<=n; i++) {
    string u;
    u += s.substr(i, n - i + 1);
    u += "?";
    u += t.substr(1, m); // ~ 6000
    vector<int> lpsu = prefix_function(u);
    string v;
    v += reversed(s.substr(1, i-1));
    v += "?";
    v += reversed(t.substr(1, m));
    vector<int> lpsv = prefix_function(v);
    
    for(int j=1; j<m; j++) { // take [1, j]
      // j = 1: n - i + 2
      // j = x: n - i + x + 1 (0 based)
      int suf = lpsu[n-i+j+1];
      int pre = lpsv[i+m-j-1];
      // answer = pre + suf
      int inds = i - pre;
      int indt = j - suf + 1;
      upd_ans(pre + suf, inds, indt);
 
    }
  }
  reverse(t.begin() + 1, t.end());
 
  for(int i=2; i<=n; i++) {
    string u;
    u += s.substr(i, n - i + 1);
    u += "?";
    u += t.substr(1, m); // ~ 6000
    vector<int> lpsu = prefix_function(u);
    string v;
    v += reversed(s.substr(1, i-1));
    v += "?";
    v += reversed(t.substr(1, m));
    vector<int> lpsv = prefix_function(v);
    /*
    cout << u << "\n";
    for(int x: lpsu) cout << x << " ";
    cout << "\n";
    cout << v << "\n";
    for(int x: lpsv) cout << x << " ";
    cout << "\n";
    */
    for(int j=1; j<m; j++) { // take [1, j]
      // j = 1: n - i + 2
      // j = x: n - i + x + 1 (0 based)
      int suf = lpsu[n-i+j+1];
      int pre = lpsv[i+m-j-1];
      // answer = pre + suf
      int inds = i - pre;
      int indt = j + pre;
      indt = m - indt + 1;
      upd_ans(pre + suf, inds, indt);
 
    }
  }
 
  reverse(t.begin() + 1, t.end());
  
  // Remove whitespace
  s = s.substr(1, n);
  t = t.substr(1, m);
  // 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) m - 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);
}

• Subtask 1: 15 / 15