AtCoder Beginner Contest 138 E - Strings of Impurity 誤答コード(Resolved)

問題はこちら。

atcoder.jp

誤答コード

#include <bits/stdc++.h>
using namespace std;
using P = pair<int, int>;

int main() {
  string s, t;
  bool yes = true;
  cin >> s >> t;
  int n = s.size();
  s += s;
  vector<vector<int>> ss(26);
  vector<vector<int>> tt(26);
  for(int i=0;i<s.size();i++) {
    ss[s[i]-'a'].emplace_back(i);
  }
  for(int i=0;i<t.size();i++) {
    tt[t[i]-'a'].emplace_back(i);
  }
  for(int i=0;i<26;i++) {
    if(tt[i].size() != 0 && ss[i].size() == 0) yes = false;
  }
  if(!yes) {
    cout << -1 << endl;
    return 0;
  }
  vector<vector<int>> next(n, vector<int>(26));
  for(int i=0;i<n;i++) {
    for(int j=0;j<26;j++) {
      if(ss[j].size() == 0) next[i][j] = INT_MAX;
      else {
        auto it = upper_bound(ss[j].begin(), ss[j].end(), i);
        next[i][j] = *it - i;
      }
    }
  }
  long long ans = 0;
  for(int i=0;i<t.size();i++) {
    int id = t[i] - 'a';
    int pos = ans % n;
    ans += next[pos][id];
  }
  cout << ans + 1LL << endl;
}

ところどころWAになっていてデバッグがしづらい。回収する誤答コードが増えてきたなぁ。早いところ回収せねば。。

追記用

（2020年3月27日追記）

最後のfor文のところでi==0の時を例外として処理するのを忘れていた。i==0の時最初の地点の文字も候補として含めて良い。しかし上のコードでは一番初めの文字が除外されている。それを修正しAC。