Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3665

Problem Lang User Status Time Memory
Suffix Array cpp (anonymous) AC 85 ms 12.84 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 63 ms 8.70 MiB
all_same_01 AC 65 ms 8.81 MiB
all_same_02 AC 63 ms 8.77 MiB
all_same_03 AC 62 ms 8.68 MiB
all_same_04 AC 61 ms 8.65 MiB
example_00 AC 6 ms 0.66 MiB
example_01 AC 5 ms 0.59 MiB
example_02 AC 6 ms 0.55 MiB
example_03 AC 6 ms 0.61 MiB
fib_str_00 AC 69 ms 11.90 MiB
fib_str_01 AC 52 ms 9.23 MiB
fib_str_02 AC 53 ms 9.34 MiB
fib_str_03 AC 46 ms 7.22 MiB
fib_str_04 AC 69 ms 12.41 MiB
max_random_00 AC 85 ms 12.16 MiB
max_random_01 AC 84 ms 12.83 MiB
max_random_02 AC 85 ms 12.84 MiB
max_random_03 AC 83 ms 12.82 MiB
max_random_04 AC 85 ms 12.12 MiB
random_00 AC 68 ms 9.76 MiB
random_01 AC 80 ms 11.45 MiB
random_02 AC 13 ms 1.80 MiB
random_03 AC 74 ms 10.70 MiB
random_04 AC 50 ms 7.26 MiB

#include <bits/stdc++.h> ///////////////// // SuffixArray // ///////////////// class SuffixArray { private: std::vector<int> result_; // 文字列のコード(>0)を受け取る. // 番兵0は呼び出し元で入れておく. std::vector<int> sais(const std::vector<int>& array, const int char_num) const { const int size{(int)array.size()}; if (size == 1) return {0}; // S型L型の判定 std::vector<bool> isSmall(size); isSmall.back() = true; for (int i{size - 2}; i >= 0; i--) { if (array[i] < array[i + 1]) isSmall[i] = true; else if (array[i] > array[i + 1]) isSmall[i] = false; else isSmall[i] = isSmall[i + 1]; } // バケットの作成 // iのためのバケットは[bucket[i - 1], bucket[i])で表される. std::vector<int> bucket(char_num + 1); for (const auto& num: array) bucket[num]++; for (int i{}; i < char_num; i++) bucket[i + 1] += bucket[i]; // LMS-substringのソートの為のinduced sort // lmsIndicesにはLMSの位置が昇順に入る std::vector<int> lmsIndices; lmsIndices.reserve(size >> 1); for (int i{1}; i < size; i++) if (isSmall[i] && !isSmall[i - 1]) lmsIndices.push_back(i); std::vector<int> suffixArray(inducedSort(array, char_num, isSmall, bucket, lmsIndices)); // lmsIndicesの逆写像 std::vector<int> lmsIndicesInv(size, -1); for (int i{}; i < (int)lmsIndices.size(); i++) lmsIndicesInv[lmsIndices[i]] = i; // LMS-substringのコード化 // codeArray:LMS-substringのコードがarrayに出てくる順番に入る. std::vector<int> codeArray(lmsIndices.size()); int code_num{}; for (int i{1}, prev_begin{size - 1}, prev_end{size}; i < size; i++) { const int& begin{suffixArray[i]}; if (begin == 0) continue; if (!isSmall[begin] || isSmall[begin - 1]) continue; int end{lmsIndices[lmsIndicesInv[begin] + 1] + 1}; if (!areEqual(array.begin() + begin, array.begin() + end, array.begin() + prev_begin, array.begin() + prev_end)) code_num++; codeArray[lmsIndicesInv[begin]] = code_num; prev_begin = begin; prev_end = end; } // LMS-substringのsuffix array std::vector<int> lmsSA{sais(codeArray, code_num)}; // 正しいinduced sort std::vector<int> sortedLmsIndices(lmsIndices.size()); for (int i{}; i < (int)lmsIndices.size(); i++) sortedLmsIndices[(int)lmsIndices.size() - 1 - i] = lmsIndices[lmsSA[i]]; return inducedSort(array, char_num, isSmall, bucket, sortedLmsIndices); } template <typename Iterator> bool areEqual(const Iterator begin1, const Iterator end1, const Iterator begin2, const Iterator end2) const { if (end1 - begin1 != end2 - begin2) return false; for (int i{}; begin1 + i != end1; i++) if (begin1[i] != begin2[i]) return false; return true; } std::vector<int> inducedSort(const std::vector<int>& array, const int char_num, const std::vector<bool>& isSmall, const std::vector<int>& bucket, const std::vector<int>& lmsIndices) const { // lmsの追加 const int size{(int)array.size()}; std::vector<int> suffixArray(size, -1); std::vector<int> moveCounter(char_num + 1); for (auto& lms_i: lmsIndices) { moveCounter[array[lms_i]]++; suffixArray[bucket[array[lms_i]] - moveCounter[array[lms_i]]] = lms_i; } std::fill(moveCounter.begin(), moveCounter.end(), 0); // L型の追加 for (auto& num: suffixArray) { if (num <= 0) continue; const int& next{array[num - 1]}; if (isSmall[num - 1]) continue; suffixArray[bucket[next - 1] + moveCounter[next]] = num - 1; moveCounter[next]++; } std::fill(moveCounter.begin(), moveCounter.end(), 0); // S型の追加 for (int i{size - 1}; i > 0; i--) { const int& now{suffixArray[i]}; if (now == 0) continue; const int& next{array[now - 1]}; if (!isSmall[now - 1]) continue; moveCounter[next]++; suffixArray[bucket[next] - moveCounter[next]] = now - 1; } return suffixArray; } public: const std::vector<int>& result; SuffixArray(const std::string& str, const char initial_char = 'a') : result(result_) { // 文字列のコード化 std::vector<int> numberArray(str.size() + 1); for (int i{}; i < (int)str.size(); i++) numberArray[i] = str[i] - initial_char + 1; result_ = sais(numberArray, 26); } }; int main() { std::string S; std::cin >> S; auto sa{SuffixArray(S).result}; for (int i{1}; i < (int)sa.size(); i++) printf("%d%c", sa[i], i + 1 == (int)sa.size()? '\n': ' '); return 0; }