test/aoj/jag/rolling_hash.2.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

• Montgomery modular multiplication (lib/internal/internal_math.hpp)
• lib/math/modint.hpp
• ローリングハッシュ (lib/string/rolling_hash.hpp)

Code

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

using Mint = modint107;

int main(void) {
    int m;
    std::cin >> m;
    rolling_hash rh;
    std::unordered_set<std::uint64_t> st;
    std::vector<int> lens;
    std::string t;
    for (int i = 0; i < m; ++i) {
        std::cin >> t;
        st.emplace(rh.hash(t));
        lens.emplace_back(t.size());
    }
    std::sort(lens.begin(), lens.end());
    lens.erase(std::unique(lens.begin(), lens.end()), lens.end());
    std::string s;
    std::cin >> s;
    rolling_hash rhs(s, rh.get_base());
    int n = s.size();
    std::vector<Mint> dp(n + 1);
    dp[0] = 1;
    for (int i = 1; i < n + 1; ++i) {
        for (int x : lens) {
            if (i < x) break;
            if (st.count(rhs.get(i - x, i))) dp[i] += dp[i - x];
        }
    }
    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/rolling_hash.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	3 ms	3 MB
g++	00_sample_01	AC	2 ms	3 MB
g++	00_sample_02	AC	2 ms	3 MB
g++	00_sample_03	AC	2 ms	4 MB
g++	10_rand_00	AC	25 ms	5 MB
g++	10_rand_01	AC	71 ms	5 MB
g++	10_rand_02	AC	60 ms	6 MB
g++	10_rand_03	AC	116 ms	5 MB
g++	10_rand_04	AC	69 ms	5 MB
g++	11_rand_00	AC	94 ms	6 MB
g++	11_rand_01	AC	107 ms	6 MB
g++	11_rand_02	AC	98 ms	6 MB
g++	11_rand_03	AC	79 ms	6 MB
g++	11_rand_04	AC	84 ms	6 MB
g++	20_fixed_length_00	AC	16 ms	6 MB
g++	20_fixed_length_01	AC	16 ms	6 MB
g++	20_fixed_length_02	AC	16 ms	6 MB
g++	21_fixed_length_00	AC	11 ms	6 MB
g++	21_fixed_length_01	AC	11 ms	6 MB
g++	21_fixed_length_02	AC	10 ms	6 MB
g++	22_fixed_length_00	AC	12 ms	6 MB
g++	22_fixed_length_01	AC	12 ms	6 MB
g++	22_fixed_length_02	AC	12 ms	6 MB
g++	23_fixed_length_00	AC	11 ms	6 MB
g++	23_fixed_length_01	AC	11 ms	6 MB
g++	23_fixed_length_02	AC	11 ms	6 MB
g++	24_fixed_length_00	AC	11 ms	6 MB
g++	24_fixed_length_01	AC	11 ms	6 MB
g++	24_fixed_length_02	AC	11 ms	6 MB
g++	30_mixed_length_00	AC	14 ms	6 MB
g++	30_mixed_length_01	AC	13 ms	6 MB
g++	30_mixed_length_02	AC	13 ms	6 MB
g++	30_mixed_length_03	AC	14 ms	6 MB
g++	30_mixed_length_04	AC	14 ms	6 MB
g++	90_challenge_00	AC	22 ms	6 MB
g++	90_challenge_01	AC	371 ms	6 MB
g++	90_challenge_02	AC	21 ms	6 MB
g++	90_challenge_03	AC	362 ms	6 MB
g++	90_challenge_04	AC	14 ms	6 MB
g++	90_challenge_05	AC	2 ms	4 MB

Back to top page