Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3668

Problem Lang User Status Time Memory
Suffix Array cpp (anonymous) AC 76 ms 12.27 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 58 ms 8.67 MiB
all_same_01 AC 57 ms 8.71 MiB
all_same_02 AC 58 ms 8.75 MiB
all_same_03 AC 58 ms 8.71 MiB
all_same_04 AC 57 ms 8.59 MiB
example_00 AC 6 ms 1.05 MiB
example_01 AC 7 ms 1.14 MiB
example_02 AC 8 ms 1.09 MiB
example_03 AC 8 ms 1.05 MiB
fib_str_00 AC 66 ms 11.34 MiB
fib_str_01 AC 52 ms 9.07 MiB
fib_str_02 AC 51 ms 9.45 MiB
fib_str_03 AC 44 ms 7.54 MiB
fib_str_04 AC 66 ms 12.27 MiB
max_random_00 AC 76 ms 11.33 MiB
max_random_01 AC 76 ms 11.40 MiB
max_random_02 AC 76 ms 11.41 MiB
max_random_03 AC 75 ms 11.45 MiB
max_random_04 AC 76 ms 11.29 MiB
random_00 AC 61 ms 9.22 MiB
random_01 AC 72 ms 10.81 MiB
random_02 AC 14 ms 2.28 MiB
random_03 AC 68 ms 10.07 MiB
random_04 AC 43 ms 6.92 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()}; // 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] = array[i] < array[i + 1]; 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; if (code_num + 1 == (int)codeArray.size()) { lmsSA.resize(codeArray.size()); for (int i{}; i < (int)codeArray.size(); i++) lmsSA[codeArray[i]] = i; } else 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(500'005, '\n'); for (int i{}; i == 0 || S[i - 1] != '\n'; i++) S[i] = getchar(); while (S.back() == '\n') S.pop_back(); 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; }