[AtCoder] ABC 138 E – Strings of Impurity

2019年8月20日

問題

方針

シミュレーション

\( t \) に含まれる文字が \( s \) に存在しなければ、条件を満たす整数は存在しません。そうではないとき、\( t \) の \( i \) 文字目 \( t_i \) について、\( s’ \) の先頭から調べていき、\( t_i \) に一致する文字の箇所を見つけます。次に、\( t_{i + 1} \) についてその一致した箇所以降の文字列から \( t_{i + 1} \) を見つけます。このようにしていけば、条件を満たす \( s’ \) の最小の部分文字列の長さが分かります。

二分探索

ある文字 \( i \ (1 \leq i \leq 26)\) が \( s \) のどの位置に存在するかというリストが昇順に整列されたものを \( k(i, j) \) とします。このとき、\( k(i, j) \) は文字 \( i \) が \( s \) の \( j \) 番目に現れるときの \( s \) の添え字となります。

まず初めに、\( s \) を必要な回数連結するイメージで考えます。整数 \( t \ (1 \leq t \leq |s|) \) の初期値を \( 1 \) とします。\( t \) の先頭の文字から調べていき、\( t \leq k(t_i, j) \) を満たす最小の \( j \) が存在するとき、新たに \( s \) を連結する必要がありません。そうではないとき、新たに \( s \) を連結させる必要があります。連結させる必要がないとき、\( t = k(t_i, j) + 1 \) と更新し、そうでなければ、\( t = 1 \) と更新します。

連結させる必要がないとき、新たに増える文字の長さは、\( k(t_i, j) – t + 1\) となり、そうではないとき、\( t \) 以降の文字列分の長さ \( |s| – t + 1\) と \( s \) を先頭から調べた時に新たに増える文字列の長さ \( k(t_i, 1) \) を加算したものとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
  string s, t;
  cin >> s >> t;
  int c1[26]{}, c2[26]{};
  vector<int> k[26];
  for (int i = 0; i < s.length(); i++) {
    c1[s[i] - 'a']++;
    k[s[i] - 'a'].push_back(i + 1);
  }
  for (int i = 0; i < t.length(); i++) {
    c2[t[i] - 'a']++;
  }
  for (int i = 0; i < 26; i++) {
    if (c2[i] != 0 && c1[i] == 0) {
      cout << "-1\n";
      return 0;
    }
  }
  ll idx = 1;
  ll l = s.length();
  ll ans = 0;
  for (int i = 0; i < t.length(); i++) {
    int j = t[i] - 'a';
    auto iter = lower_bound(k[j].begin(), k[j].end(), idx);
    int v = iter - k[j].begin();
    if (v == k[j].size()) {
      ans += (l -  idx + 1);
      ans += (ll)(k[j][0]);
      idx = k[j][0] + 1;
    } else {
      ans += (ll)(k[j][v] - idx + 1);
      idx = k[j][v] + 1;
    }
  }
  cout << ans << "\n";
  return 0;
}