test/yosupo/string/number_of_substring.test.cpp

• View this file on GitHub
• Last update: 2025-05-14 10:33:39+09:00
• Problem: https://judge.yosupo.jp/problem/number_of_substrings

Depends on

• Suffix Array (lib/string/suffix_array.hpp)

Code

// competitive-verifier: PROBLEM https://judge.yosupo.jp/problem/number_of_substrings
#include <cstdint>
#include <iostream>
#include <vector>
#include "string/suffix_array.hpp"

int main(void) {
    std::string s;
    std::cin >> s;
    auto sa = suffix_array(s);
    auto v = lcp_array(s, sa);
    int n = s.size();
    std::int64_t ans = std::int64_t(n) * (n + 1) / 2;
    for (auto x : v) ans -= x;
    std::cout << ans << '\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/suffix_array.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	all_same_00	AC	22 ms	12 MB
g++	all_same_01	AC	22 ms	12 MB
g++	all_same_02	AC	22 ms	12 MB
g++	all_same_03	AC	22 ms	12 MB
g++	all_same_04	AC	22 ms	12 MB
g++	example_00	AC	2 ms	4 MB
g++	example_01	AC	2 ms	4 MB
g++	example_02	AC	2 ms	3 MB
g++	example_03	AC	2 ms	3 MB
g++	fib_str_00	AC	39 ms	15 MB
g++	fib_str_01	AC	29 ms	12 MB
g++	fib_str_02	AC	33 ms	13 MB
g++	fib_str_03	AC	23 ms	10 MB
g++	fib_str_04	AC	45 ms	16 MB
g++	max_random_00	AC	61 ms	16 MB
g++	max_random_01	AC	62 ms	16 MB
g++	max_random_02	AC	63 ms	16 MB
g++	max_random_03	AC	63 ms	16 MB
g++	max_random_04	AC	62 ms	16 MB
g++	random_00	AC	50 ms	13 MB
g++	random_01	AC	59 ms	15 MB
g++	random_02	AC	8 ms	5 MB
g++	random_03	AC	54 ms	14 MB
g++	random_04	AC	34 ms	10 MB

Back to top page