Submit Info #3039

Problem Lang User Status Time Memory
Number of Substrings cpp knuu AC 1138 ms 11.22 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 755 ms 11.06 MiB
all_same_01 AC 758 ms 11.14 MiB
all_same_02 AC 750 ms 11.18 MiB
all_same_03 AC 749 ms 11.14 MiB
all_same_04 AC 750 ms 11.09 MiB
example_00 AC 6 ms 0.64 MiB
example_01 AC 6 ms 0.68 MiB
example_02 AC 7 ms 0.64 MiB
example_03 AC 5 ms 0.61 MiB
fib_str_00 AC 1138 ms 11.22 MiB
fib_str_01 AC 787 ms 8.47 MiB
fib_str_02 AC 729 ms 8.02 MiB
fib_str_03 AC 664 ms 7.43 MiB
fib_str_04 AC 1127 ms 11.01 MiB
max_random_00 AC 1068 ms 11.13 MiB
max_random_01 AC 1068 ms 11.10 MiB
max_random_02 AC 1071 ms 11.14 MiB
max_random_03 AC 1064 ms 11.18 MiB
max_random_04 AC 1065 ms 11.02 MiB
random_00 AC 806 ms 8.98 MiB
random_01 AC 989 ms 10.51 MiB
random_02 AC 66 ms 1.76 MiB
random_03 AC 917 ms 9.75 MiB
random_04 AC 499 ms 6.60 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(const std::string &T) const { 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() { // https://judge.yosupo.jp/problem/suffixarray 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; }