Submit Info #3038

Problem Lang User Status Time Memory
Number of Substrings cpp knuu AC 1151 ms 11.18 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 768 ms 11.04 MiB
all_same_01 AC 779 ms 11.08 MiB
all_same_02 AC 780 ms 11.12 MiB
all_same_03 AC 775 ms 11.17 MiB
all_same_04 AC 779 ms 11.04 MiB
example_00 AC 6 ms 0.55 MiB
example_01 AC 6 ms 0.64 MiB
example_02 AC 6 ms 0.66 MiB
example_03 AC 6 ms 0.55 MiB
fib_str_00 AC 1151 ms 11.16 MiB
fib_str_01 AC 791 ms 8.41 MiB
fib_str_02 AC 737 ms 8.05 MiB
fib_str_03 AC 661 ms 7.42 MiB
fib_str_04 AC 1128 ms 10.97 MiB
max_random_00 AC 1070 ms 11.04 MiB
max_random_01 AC 1078 ms 11.18 MiB
max_random_02 AC 1090 ms 11.16 MiB
max_random_03 AC 1094 ms 11.07 MiB
max_random_04 AC 1080 ms 11.12 MiB
random_00 AC 814 ms 8.89 MiB
random_01 AC 996 ms 10.44 MiB
random_02 AC 68 ms 1.76 MiB
random_03 AC 917 ms 9.77 MiB
random_04 AC 491 ms 6.61 MiB

#include <functional> #include <iostream> #include <string> #include <vector> struct SuffixArray { int N, k; std::string S; std::vector<int> sa, rank, tmp; std::vector<int> lcp, rank_lcp; SuffixArray(std::string S) : N(S.size()), S(S), sa(N + 1), rank(N + 1), tmp(N + 1) { construct(); } void construct() { for (int i = 0; i <= N; i++) { sa[i] = i; rank[i] = i < N ? S[i] : -1; } std::function<bool(int, int)> compare = [&](int i, int j) { if (rank[i] != rank[j]) { return rank[i] < rank[j]; } else { int ri = i + k <= N ? rank[i + k] : -1; int rj = j + k <= N ? rank[j + k] : -1; return ri < rj; } }; for (k = 1; k <= N; k *= 2) { sort(sa.begin(), sa.end(), compare); tmp[sa[0]] = 0; for (int i = 1; i <= N; i++) { tmp[sa[i]] = tmp[sa[i - 1]] + (compare(sa[i - 1], sa[i]) ? 1 : 0); } for (int i = 0; i <= N; i++) rank[i] = tmp[i]; } } bool contain(std::string T) { int left = 0, right = N; while (left + 1 < right) { int mid = (left + right) / 2; (S.compare(sa[mid], T.length(), T) < 0 ? left : right) = mid; } return S.compare(sa[right], T.length(), T) == 0; } void construct_lcp() { lcp.resize(N), rank_lcp.resize(N + 1); for (int i = 0; i <= N; i++) rank_lcp[sa[i]] = i; int h = 0; lcp[0] = 0; for (int i = 0; i < N; i++) { int j = sa[rank[i] - 1]; if (h > 0) h--; for (; j + h < N and i + h < N; h++) { if (S[j + h] != S[i + h]) break; } lcp[rank[i] - 1] = h; } } }; void yosupo() { std::string S; std::cin >> S; SuffixArray sa(S); for (size_t i = 1; i <= S.size(); i++) { std::cout << sa.sa[i] << (i == S.size() ? '\n' : ' '); } } void yosupo2() { // https://judge.yosupo.jp/problem/number_of_substrings std::string S; std::cin >> S; SuffixArray sa(S); sa.construct_lcp(); long long ans = 1LL * S.size() * (S.size() + 1) / 2; for (size_t i = 0; i < S.size(); i++) { ans -= sa.lcp[i]; } std::cout << ans << std::endl; } int main() { std::cin.tie(0); std::ios_base::sync_with_stdio(false); // yosupo(); yosupo2(); return 0; }