Submission #7064940

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i, n) for (ll i = 0; i < (n); i++)
#define rep2(i, a, b) for (ll i = (a); i < (b); i++)
typedef uint64_t ull;
typedef int64_t ll;
typedef std::pair<ll, ll> PLL;

using namespace std;

set<ll> can[300];
ll ans[100100];

signed main() {
  string s, t;
  cin >> s >> t;
  ll ns = s.size(), nt = t.size();
  rep(i, ns) {
    can[s[i]].insert(i);
  }
  rep(i, 300) {
    if (can[i].size() == 0)
      continue;
    auto mi = *can[i].begin();
    can[i].insert(mi + ns);
    //printf("%c :", i);
    //for (auto c : can[i]) {
    //  printf("%d ", c);
    //}
    //printf("\n");
  }

  // printf("ans: ");
  ll pos = -1;
  rep(i, nt) {
    if (can[t[i]].size() == 0) {
      cout << -1 << endl;
      return 0;
    }
    ll now = pos % ns;
    ll nxt = *can[t[i]].lower_bound((pos+1) % ns);
    if (nxt > now) {
      pos = pos + (nxt-now);
    } else {
      pos = pos + (ns+nxt-now);
    }
    ans[i] = pos;
    //printf("%d ", ans[i]);
  }
  //printf("\n");
  cout << ans[nt-1] + 1 << endl;
  return 0;
}

Submission Info

Judge Result