\(S\) および \(T _ i\) に含まれるどの文字より辞書順で小さな文字 ` と、辞書順で大きな文字 {, } ({\({}\lt{}\)}) を加えた文字集合 \(\Sigma\) の文字列を考えます（ \(\sigma=|\Sigma|\leq29\) です）。

文字列 \(C\) を \(C=S+{}\){\({}+T _ 1+{}\)`\({}+T _ 1+{}\)}\({}+T _ 2+\cdots+{}\)}\({}+T _ Q+{}\)`\({}+T _ Q+{}\)} として定めます。 \(C\) は長さ \(L=\displaystyle|S|+2\sum _ {i=1} ^ Q|T _ i|+2Q+1\) の文字列です。

\(C\) の Suffix Array の値 \((\operatorname{SA} _ C[i]) _ {1\leq i\leq L}\) に対して、処理すべきクエリは以下のようになります。

• \(T _ i+{}\)` の先頭を \(C\) の \(L _ i\) 文字目、\(T _ i+{}\)} の先頭を \(C\) の \(U _ i\) 文字目とする。\(\operatorname{SA} _ C\) で \(L _ i\) と \(U _ i\) に挟まれた値のうち、値が \(|S|\) 以下のものはいくつあるか？

これは、事前に \(L _ i,U _ i\) を求めておき、\(C\) の Suffix Array を先頭からみることで解くことができます。

Suffix Array は文字列長に対して線形時間で構築できるので、時間計算量は \(O(|S|+\sum |T _ i|+\sigma)\) などでこの問題を解くことができます。

実装例は以下のようになります。

以下の実装例では \(L _ i,U _ i\) から \(i\) を求める際にハッシュテーブルを用いているため空間計算量が \(O(Q)\) ワードで時間計算量が expected \(O(|S|+\sum |T _ i|+\sigma)\) となっていますが、追加で \(O((|S|+\sum |T _ i|)\log Q)\) bit 程度の空間を使うことで時間計算量を worst にすることもできます。

#include <iostream>
#include <unordered_map>
#include <algorithm>

#include <atcoder/string>

int main() {
    using namespace std;
    string S;
    cin >> S;
    unsigned N(size(S)), Q;
    cin >> Q;

    // Li, Ui から i を求める
    unordered_map<unsigned, unsigned> concatenated_idx_to_query;

    // 与えられる文字列を連結してできる列（連結する際に値を 0 以上 28 以下になおす）
    vector<int> concat;

    // S + { を追加
    ranges::transform(S, back_inserter(concat), [](auto c){return c - '`';});
    concat.emplace_back(27);

    for(unsigned i{}; i < Q; ++i){
        string T;
        cin >> T;
        // Li をメモ
        concatenated_idx_to_query[size(concat)] = i;
        // Ti + ` を追加
        ranges::transform(T, back_inserter(concat), [](auto c){return c - '`';});
        concat.emplace_back();

        // Ui をメモ
        concatenated_idx_to_query[size(concat)] = i;
        // Ti + } を追加
        ranges::transform(T, back_inserter(concat), [](auto c){return c - '`';});
        concat.emplace_back(28);
    }

    vector<unsigned> ans(Q);
    // counter := これまでに出てきた S の部分文字列に対応するインデックスの個数
    for(unsigned counter{}; const auto idx : atcoder::suffix_array(concat, 28)){
        if(idx < N)
            ++counter;
        if (concatenated_idx_to_query.contains(idx))
            (ans[concatenated_idx_to_query[idx]] *= -1) += counter;
    }

    for(const auto a : ans)
        cout << a << '\n';
    cout << endl;
    return 0;
}