test/aoj/jag/aho_corasick.test.cpp

• View this file on GitHub
• Last update: 2025-07-08 15:34:19+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/2863

Depends on

• 重み付きグラフ (lib/graph/graph.hpp)
• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• lib/math/modint.hpp
• Aho Corasick法 (lib/string/aho_corasick.hpp)
• 木の距離を求める (lib/tree/tree_function.hpp)

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2863
#include "string/aho_corasick.hpp"
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include "math/modint.hpp"
#include "tree/tree_function.hpp"

using Mint = modint107;

int main(void) {
    int m;
    std::cin >> m;
    std::vector<std::string> t(m);
    for (auto &e : t) std::cin >> e;
    aho_corasick<26, 'a'> aho;
    std::vector<std::vector<int>> correct;
    for (int i = 0; i < m; ++i) {
        auto v = aho.insert(t[i]);
        correct.resize(aho.size());
        correct[v.back()].emplace_back(i);
    }
    aho.build();
    auto failure = aho.failures();
    auto bfs = tree_bfs(failure);
    for (auto x : bfs) {
        int y = failure[x];
        std::vector<int> v;
        std::set_union(correct[x].begin(), correct[x].end(), correct[y].begin(), correct[y].end(),
                       std::back_inserter(v));
        correct[x] = v;
    }
    std::string s;
    std::cin >> s;
    int n = s.size();
    auto res = aho.search(s);
    std::vector<Mint> dp(n + 1);
    dp[0] = 1;
    for (int i = 0; i < n + 1; ++i) {
        for (auto y : correct[res[i]]) dp[i] += dp[i - t[y].size()];
    }
    std::cout << dp.back() << '\n';

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: string/aho_corasick.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	2 ms	3 MB
g++	00_sample_01	AC	2 ms	4 MB
g++	00_sample_02	AC	2 ms	4 MB
g++	00_sample_03	AC	2 ms	4 MB
g++	10_rand_00	AC	65 ms	40 MB
g++	10_rand_01	AC	61 ms	43 MB
g++	10_rand_02	AC	73 ms	43 MB
g++	10_rand_03	AC	70 ms	49 MB
g++	10_rand_04	AC	41 ms	28 MB
g++	11_rand_00	AC	78 ms	53 MB
g++	11_rand_01	AC	75 ms	50 MB
g++	11_rand_02	AC	78 ms	52 MB
g++	11_rand_03	AC	77 ms	50 MB
g++	11_rand_04	AC	79 ms	51 MB
g++	20_fixed_length_00	AC	79 ms	41 MB
g++	20_fixed_length_01	AC	83 ms	41 MB
g++	20_fixed_length_02	AC	79 ms	43 MB
g++	21_fixed_length_00	AC	58 ms	52 MB
g++	21_fixed_length_01	AC	58 ms	52 MB
g++	21_fixed_length_02	AC	58 ms	52 MB
g++	22_fixed_length_00	AC	76 ms	51 MB
g++	22_fixed_length_01	AC	78 ms	52 MB
g++	22_fixed_length_02	AC	75 ms	50 MB
g++	23_fixed_length_00	AC	71 ms	53 MB
g++	23_fixed_length_01	AC	70 ms	52 MB
g++	23_fixed_length_02	AC	69 ms	53 MB
g++	24_fixed_length_00	AC	64 ms	53 MB
g++	24_fixed_length_01	AC	63 ms	52 MB
g++	24_fixed_length_02	AC	64 ms	51 MB
g++	30_mixed_length_00	AC	76 ms	54 MB
g++	30_mixed_length_01	AC	75 ms	51 MB
g++	30_mixed_length_02	AC	75 ms	51 MB
g++	30_mixed_length_03	AC	72 ms	51 MB
g++	30_mixed_length_04	AC	75 ms	53 MB
g++	90_challenge_00	AC	17 ms	7 MB
g++	90_challenge_01	AC	78 ms	6 MB
g++	90_challenge_02	AC	14 ms	7 MB
g++	90_challenge_03	AC	45 ms	5 MB
g++	90_challenge_04	AC	18 ms	9 MB
g++	90_challenge_05	AC	2 ms	4 MB

Back to top page