#1142552 (C++23) No.430 文字列検索

• 問題: No.430 文字列検索
• ユーザー: 👑 loop0919
• 提出日時: 2026-01-02 17:44:40
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 16 ms / 2,000 ms
• コード長: 4,491 bytes
• コンパイル時間: 4,200 ms
• コンパイル使用メモリ: 361,148 KB
• 実行使用メモリ: 7,848 KB
• 最終ジャッジ日時: 2026-01-02 17:44:47
• 合計ジャッジ時間: 5,447 ms
• ジャッジサーバーID （参考情報）: judge3 / judge1

ファイルパターン	結果
sample	AC * 4
other	AC * 14

ソースコード

/**
 * author: loop0919
 */

#include <bits/stdc++.h>

class AhoCorasick {
public:
    static constexpr int ROOT = 0;

private:
    int sigma_ = 0;

    // 文字 -> index
    std::unordered_map<char, int> to_index_;

    // graph_[v][c] = next vertex (build前は -1 / build後は必ず埋まる)
    std::vector<std::vector<int>> graph_;

    // end_[v] = その頂点でマッチ完了する pattern id の集合（build で failure 側も統合）
    std::vector<std::vector<int>> end_;

    // pattern id -> 長さ
    std::vector<int> length_;

public:
    // letters: 使用する文字集合（例: 英小文字）
    explicit AhoCorasick(const std::string& letters = "abcdefghijklmnopqrstuvwxyz") {
        sigma_ = static_cast<int>(letters.size());
        to_index_.reserve(static_cast<std::size_t>(sigma_) * 2);

        for (int i = 0; i < sigma_; i++) {
            to_index_[letters[i]] = i;
        }

        graph_.assign(1, std::vector<int>(sigma_, -1));
        end_.assign(1, std::vector<int>{});
        length_.clear();
    }

    void add(const std::string& pattern) {
        const int id = static_cast<int>(length_.size());
        length_.push_back(static_cast<int>(pattern.size()));
        add_impl_(pattern, id);
    }

    void build() {
        std::vector<int> link(graph_.size(), ROOT);
        std::queue<int> q;

        // ROOT の遷移を埋める
        for (int i = 0; i < sigma_; i++) {
            if (graph_[ROOT][i] == -1) {
                graph_[ROOT][i] = ROOT;
            } else {
                link[graph_[ROOT][i]] = ROOT;
                q.push(graph_[ROOT][i]);
            }
        }

        while (!q.empty()) {
            const int curr = q.front();
            q.pop();

            // end_[curr] に end_[link[curr]] を集合としてマージ
            if (!end_[link[curr]].empty()) {
                auto& a = end_[curr];
                const auto& b = end_[link[curr]];
                a.insert(a.end(), b.begin(), b.end());
                std::sort(a.begin(), a.end());
                a.erase(std::unique(a.begin(), a.end()), a.end());
            }

            for (int i = 0; i < sigma_; i++) {
                const int to = graph_[curr][i];
                if (to == -1) {
                    graph_[curr][i] = graph_[link[curr]][i];
                } else {
                    link[to] = graph_[link[curr]][i];
                    q.push(to);
                }
            }
        }
    }

    std::vector<std::vector<int>> find_all(const std::string& text, int start = ROOT) const {
        std::vector<std::vector<int>> found(length_.size());
        int curr = start;

        for (int i = 0; i < static_cast<int>(text.size()); i++) {
            auto it = to_index_.find(text[i]);
            if (it == to_index_.end()) {
                throw std::runtime_error("text contains a character not in letters");
            }
            const int index = it->second;

            curr = graph_[curr][index];
            for (int pid : end_[curr]) {
                found[pid].push_back(i - length_[pid] + 1);
            }
        }
        return found;
    }

    // --- getters ---
    const std::vector<std::vector<int>>& graph() const noexcept { return graph_; }
    const std::vector<std::vector<int>>& end() const noexcept { return end_; }

private:
    void add_impl_(const std::string& s, int id) {
        int curr = ROOT;

        for (char ch : s) {
            const int index = to_index_.at(ch);  // letters 外なら例外
            int& to = graph_[curr][index];

            if (to == -1) {
                graph_.push_back(std::vector<int>(sigma_, -1));
                end_.push_back(std::vector<int>{});
                to = static_cast<int>(graph_.size()) - 1;
            }
            curr = to;
        }

        // end_[curr] は集合的に扱いたいので重複を避ける
        auto& e = end_[curr];
        if (std::find(e.begin(), e.end(), id) == e.end()) {
            e.push_back(id);
        }
    }
};

const std::string UPPER_CASES = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

void solve() {
    std::string S;
    std::cin >> S;

    int M;
    std::cin >> M;

    AhoCorasick ac(UPPER_CASES);
    for (int _ = 0; _ < M; _++) {
        std::string C;
        std::cin >> C;
        ac.add(C);
    }

    ac.build();

    int ans = 0;
    for (auto &match: ac.find_all(S)) {
        ans += match.size();
    }

    std::cout << ans << '\n';
}

int main() {
    solve();
}