公式解説では、アルファベットサイズ \(\sigma\) に対して時間計算量 \(\displaystyle O\!\left(\sigma\sum _ {i=1} ^ Q|w _ i|\right)\) のアルゴリズムを解説しました。 この解説では、アルファベットサイズ \(\sigma\) がワードサイズの定数倍以下であることを仮定して時間計算量 \(\displaystyle O\!\left(\sigma+\sum _ {i=1} ^ Q|w _ i|\right)\) となるアルゴリズムについて話します。

高橋語で使われるが青木語では使われない文字の集合を \(C _ {\mathrm{takahashi}}\) 、青木語で使われるが高橋語では使われない文字の集合を \(C _ {\mathrm{aoki}}\) とします。 この \(2\) つの集合には共通部分がないことに注意してください。 \(C _ {\mathrm{takahashi}}\) に含まれている文字が \(w _ i\) に含まれているとき、かつそのときに限り \(w _ i\) は高橋語の単語であることが確定します。青木語についても同様です。

文字に \(0,1,\ldots,\sigma-1\) の番号 \(\operatorname{ord}\) をつけ、文字の集合 \(C\) を \(\sigma\) bit の整数 \(\displaystyle\mathrm{mask} _ C=\sum _ {c\in C}2 ^ {\operatorname{ord}( c)}\) で管理することを考えます。 すると、\(2\) つの文字の集合 \(C _ 1,C _ 2\) に共通部分があるかどうかは \(\mathrm{mask} _ {C _ 1}\) と \(\mathrm{mask} _ {C _ 2}\) のビットごとの論理積が \(0\) でないかで判定することができます。

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

#include <iostream>
#include <string>
#include <numeric>

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

    // 高橋語で使われる文字の集合
    const unsigned S_mask = transform_reduce(begin(S), end(S), 0U, bit_or{}, [](const char c){return 1U << (c - 'a');});
    // 青木語で使われる文字の集合
    const unsigned T_mask = transform_reduce(begin(T), end(T), 0U, bit_or{}, [](const char c){return 1U << (c - 'a');});

    // 高橋語でしか使われない文字の集合
    const unsigned only_takahashi = S_mask & ~T_mask;
    // 青木語でしか使われない文字の集合
    const unsigned only_aoki = ~S_mask & T_mask;

    unsigned Q;
    cin >> Q;
    for (unsigned i{}; i < Q; ++i) {
        string w;
        cin >> w;
        const unsigned w_mask = transform_reduce(begin(w), end(w), 0U, bit_or{}, [](const char c){return 1U << (c - 'a');});

        if (w_mask & only_takahashi) // 高橋語でしか使われない文字があれば
            cout << "Takahashi" << endl; // 高橋語
        else if (w_mask & only_aoki) // 青木語でしか使われない文字があれば
            cout << "Aoki" << endl; // 青木語
        else // どちらでもなければ
            cout << "Unknown" << endl; // 確定しない
    }
    return 0;
}