CF2104E AC

// Problem: E. Unpleasant Strings
// Contest: Codeforces - Educational Codeforces Round 178 (Rated for Div. 2)
// URL: https://codeforces.com/contest/2104/problem/E
// Memory Limit: 512 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include <assert.h>
#include <bits/stdc++.h>
using namespace std;
#ifndef __DEBUG__
#define dbg(...) 42
#endif
template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;

namespace rngs = std::ranges;
using ll = long long;
using a2l = array<ll, 2>;
using pll = pair<ll, ll>;
using vl = vector<ll>;

ll n, k, q;
string s;
vector<vl> ids;
vl cache;

void solve()
{
    string al;
    cin >> al;

    ll st = -1;
    for (auto c : al) {
        auto id = c - 'a';
        const auto &iv = ids[id];
        auto nit = upper_bound(iv.begin(), iv.end(), st);
        if (nit == iv.end()) {
            cout << 0 << '\n';
            return;
        }
        st = *nit;
    }

    // cache_output(st);
    cout << cache[st] + 1 << '\n';
}

int main(int argc, char **argv)
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> n >> k >> s >> q;
    ids.resize(k);

    for (ll i = 0; i < n; ++i) {
        auto id = s[i] - 'a';
        ids[id].push_back(i);
    }

    cache = vl(n + 1, -1);
    cache[n] = 0;
    for (ll i = n - 1; i >= 0; --i) {
        ll min_op = LLONG_MAX;
        for (ll id = 0; id < k; ++id) {
            const auto &iv = ids[id];
            auto nid = upper_bound(iv.begin(), iv.end(), i);
            if (nid == iv.end()) {
                min_op = 0;
                break;
            }
            min_op = min(min_op, cache[*nid] + 1);
        }
        cache[i] = min_op;
    }

    for (ll i = 0; i < q; ++i)
        solve();

    return 0;
};