/** * author: loop0919 */ #include class AhoCorasick { public: static constexpr int ROOT = 0; private: int sigma_ = 0; // 文字 -> index std::unordered_map to_index_; // graph_[v][c] = next vertex (build前は -1 / build後は必ず埋まる) std::vector> graph_; // end_[v] = その頂点でマッチ完了する pattern id の集合(build で failure 側も統合) std::vector> end_; // pattern id -> 長さ std::vector length_; public: // letters: 使用する文字集合(例: 英小文字) explicit AhoCorasick(const std::string& letters = "abcdefghijklmnopqrstuvwxyz") { sigma_ = static_cast(letters.size()); to_index_.reserve(static_cast(sigma_) * 2); for (int i = 0; i < sigma_; i++) { to_index_[letters[i]] = i; } graph_.assign(1, std::vector(sigma_, -1)); end_.assign(1, std::vector{}); length_.clear(); } void add(const std::string& pattern) { const int id = static_cast(length_.size()); length_.push_back(static_cast(pattern.size())); add_impl_(pattern, id); } void build() { std::vector link(graph_.size(), ROOT); std::queue 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> find_all(const std::string& text, int start = ROOT) const { std::vector> found(length_.size()); int curr = start; for (int i = 0; i < static_cast(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>& graph() const noexcept { return graph_; } const std::vector>& 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(sigma_, -1)); end_.push_back(std::vector{}); to = static_cast(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(); }