RUPC2018 day2 D: AABABCAC

問題ページ
Aizu Online Judge Arena

解法

1回操作すると文字列の長さは少なくとも半分になるので操作回数はO(log|S|)程度になる。
x回操作するために文字列s中にどのような文字列が必要か考える。x=1では文字列sの部分文字列としてtが存在していれば操作が可能。x=2では1回目に分割されたあとの文字列全てに部分文字列としてtが存在していれば操作が可能。例えばt="ab"であれば ab + a + ab + b + ab = abaabbab が文字列sに存在していればよい。同様にx=3では2回分割したあとに文字列全てにtが含まれていれば操作が可能となる。t="ab"であれば abaabbab + a + abaabbab + b + abaabbab が文字列s中に存在していればよい。
存在しているか確認すべき文字列は再帰的に構成することができる。部分文字列として存在しているかは前から貪欲に見ていけばよい。操作回数は高々O(log|S|)で操作できるかの確認はO(|S|)程度で可能なため全体でO(|S|log|S|)で通せる。
注意点としてつくる文字列が長くなりすぎるとMLEする。文字列長が|S|を超えていれば含まれることはないのでそこで枝刈りすると回避できる。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;
using PII = pair<int, int>;

#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)
#define REP(i, n) FOR(i, 0, n)
#define ALL(x) x.begin(), x.end()
#define PB push_back

const ll LLINF = (1LL<<60);
const int INF = (1LL<<30);
const int MOD = 1000000007;

template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); }
template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); }
template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; }
template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); }
template<class S,class T>
ostream &operator <<(ostream& out,const pair<S,T>& a){
  out<<'('<<a.first<<','<<a.second<<')';
  return out;
}
template<class T>
ostream &operator <<(ostream& out,const vector<T>& a){
  out<<'[';
  REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';}
  out<<']';
  return out;
}

int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};

signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

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

  string now = t;
  REP(i, 30) {
    // sの中にnowが含まれるか判定
    int cnt = 0;
    REP(j, s.size()) if(cnt < now.size() && s[j] == now[cnt]) cnt++;
    if(cnt < now.size()) {
      cout << i << endl;
      return 0;
    }
    int n_sz = now.size() * t.size() + now.size() + t.size();
    if(n_sz > s.size()) {
      cout << i+1 << endl;
      return 0;
    }
    string n = now;
    REP(j, t.size()) n += t[j] + now;
    now = n;
  }

  return 0;
}