2019-2020 ACM-ICPC Latin American Regional Programming Contest G. Gluing Pictures

リンク 問題文

解法

これの類題です。
文字目までの文字列を完成させるのに最小となる連続部分列の個数
とします。すると、この配列は広義単調増加になっているはずなので、
は、文字目を右端とするようなの部分文字列の中で最長の長さをとしたとき、となります。
このは前計算で求めておくことで、答えを求めることができます。
この前計算にはSuffix ArrayとLCPを用います。"<探したい文字列>#S"と連結した後にLCP配列を作成すると、探したい文字列についてのSAのインデックスの前と後ろそれぞれで、最も近い部分に存在するSの一部から始まる箇所を探します。そして、その間にあるLCPの値の最小値が、求めたいになります。
前からと後ろからそれぞれループをし、Sの部分文字列があたったらLCPの値をその値に更新、それ以外の場合は現在の値とLCPの値のminを取る、という操作を繰り返しながらメモをします。 探したい文字列それぞれについてSAを構築するとTLEするので、探したい文字列自体も、"#"であらかじめ連結します。

#include <bits/stdc++.h>
#define inf (long long)(1e18)
using namespace std;
 
struct Suffix_Array {
  string str;
  int strlen, nowlen;
  vector<long long> rank, tmp, sa, lcp;
  Suffix_Array(string news = "") {
    str = news;
    strlen = str.size();
    nowlen = 0;
    rank.resize(strlen + 1);
    tmp.resize(strlen + 1);
    sa.resize(strlen + 1);
    construct_sa();
    construct_lcp();
  }
  void construct_sa() {
    auto cmp = [&](int l, int r) {
      if(rank[l] != rank[r]) return rank[l] < rank[r];
      int rx = l + nowlen <= strlen ? rank[l + nowlen] : -1;
      int ly = r + nowlen <= strlen ? rank[r + nowlen] : -1;
      return rx < ly;
    };
 
    for(int i = 0; i <= strlen; ++i) {
      sa[i] = i;
      rank[i] = i < strlen ? str[i] : -1;
    }
    for(nowlen = 1; nowlen <= strlen; nowlen *= 2) {
      sort(sa.begin(), sa.end(), cmp);
      tmp[sa[0]] = 0;
      for(int i = 1; i <= strlen; ++i)
        tmp[sa[i]] = tmp[sa[i - 1]] +
                     (cmp(sa[i - 1], sa[i]) ? 1 : 0);
      for(int i = 0; i <= strlen; ++i) rank[i] = tmp[i];
    }
  }
  void construct_lcp() {
    lcp.resize(strlen + 1);
    for(int i = 0; i <= strlen; ++i) rank[sa[i]] = i;
    int h = 0;
    lcp[0] = 0;
    for(int i = 0; i < strlen; ++i) {
      int j = sa[rank[i] - 1];
      if(h > 0) --h;
      for(; j + h < strlen && i + h < strlen; ++h)
        if(str[j + h] != str[i + h]) break;
      lcp[rank[i] - 1] = h;
    }
  }
};
 
long long n, sid = -1;
string s;
vector<string> v;
vector<long long> res, vid, memo;
Suffix_Array sa;
 
void solve();
long long calc(int id);
 
int main() {
  cin >> s >> n;
  v.resize(n);
  for(int i = 0; i < n; ++i) cin >> v[i];
  res.resize(n);
  solve();
  for(int i = 0; i < n; ++i) cout << res[i] << endl;
  return 0;
}
 
void solve() {
  string t;
  vid.resize(n);
  for(int i = 0; i < n; ++i) {
    vid[i] = t.size();
    t += v[i] + '#';
  }
  sid = t.size();
  t += s;
  sa = Suffix_Array(t);
  long long now = 0, tsize = t.size();
  memo.assign(tsize + 1, 0);
  for(int i = 0; i < tsize; ++i) {
    if(sa.sa[i] >= sid)
      now = sa.lcp[i];
    else
      now = min(now, sa.lcp[i]);
    memo[i + 1] = max(memo[i + 1], now);
  }
  now = 0;
  for(int i = tsize - 1; i >= 0; --i) {
    if(sa.sa[i + 1] >= sid)
      now = sa.lcp[i];
    else
      now = min(now, sa.lcp[i]);
    memo[i] = max(memo[i], now);
  }
  for(int i = 0; i < n; ++i) res[i] = calc(i);
}
 
long long calc(int id) {
  long long vsize = v[id].size();
  vector<long long> dp(vsize + 1, inf),
      idmemo(vsize + 1, inf);
  dp[0] = 0;
  idmemo[0] = 0;
  for(int i = 0; i < vsize; ++i) {
    long long nowid = vid[id] + i;
    nowid = sa.rank[nowid];
    idmemo[i] = i + memo[nowid] - 1;
    auto it = lower_bound(idmemo.begin(), idmemo.end(), i);
    if(*it < i || dp[it - idmemo.begin()] == inf) continue;
    dp[i + 1] = min(dp[i + 1], dp[it - idmemo.begin()] + 1);
  }
  if(dp[vsize] == inf) return -1;
  return dp[vsize];
}