Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3663

Problem Lang User Status Time Memory
Suffix Array cpp (anonymous) AC 89 ms 13.75 MiB

ケース詳細
Name Status Time Memory
all_same_00 AC 61 ms 9.15 MiB
all_same_01 AC 63 ms 9.08 MiB
all_same_02 AC 63 ms 9.11 MiB
all_same_03 AC 62 ms 9.07 MiB
all_same_04 AC 62 ms 9.16 MiB
example_00 AC 7 ms 0.55 MiB
example_01 AC 6 ms 0.61 MiB
example_02 AC 7 ms 0.54 MiB
example_03 AC 4 ms 0.63 MiB
fib_str_00 AC 70 ms 13.55 MiB
fib_str_01 AC 54 ms 9.97 MiB
fib_str_02 AC 56 ms 10.75 MiB
fib_str_03 AC 47 ms 7.95 MiB
fib_str_04 AC 72 ms 13.71 MiB
max_random_00 AC 88 ms 13.16 MiB
max_random_01 AC 89 ms 13.75 MiB
max_random_02 AC 87 ms 13.75 MiB
max_random_03 AC 89 ms 13.71 MiB
max_random_04 AC 88 ms 13.15 MiB
random_00 AC 72 ms 10.55 MiB
random_01 AC 83 ms 12.39 MiB
random_02 AC 14 ms 2.02 MiB
random_03 AC 78 ms 11.53 MiB
random_04 AC 53 ms 7.97 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 int size{(int)array.size()}; if (size == 1) return {0}; // S型L型の判定 std::vector<char> 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 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)); // LMS-substringのコード化 std::vector<int> codeMap(size, -1); int code_num{}; codeMap.back() = 0; 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{begin + 1}; while (!isSmall[end] || isSmall[end - 1]) end++; end++; if (![&]() { for (int i{}; begin + i < end && prev_begin + i < prev_end; i++) if (array[begin + i] != array[prev_begin + i]) return false; return end - begin == prev_end - prev_begin; }() ) { code_num++; } codeMap[begin] = code_num; prev_begin = begin; prev_end = end; } std::vector<int> codeArray, codeArrayMap; codeArray.reserve(lmsIndices.size()); codeArrayMap.reserve(lmsIndices.size()); for (int i{}; i < size; i++) { if (codeMap[i] < 0) continue; codeArray.push_back(codeMap[i]); codeArrayMap.push_back(i); } // LMS-substringのsuffix array std::vector<int> lmsSA{sais(codeArray, code_num)}; // 正しいinduced sort for (int i{}; i < (int)lmsIndices.size(); i++) lmsIndices[(int)lmsIndices.size() - 1 - i] = codeArrayMap[lmsSA[i]]; return inducedSort(array, char_num, isSmall, bucket, lmsIndices); } std::vector<int> inducedSort(const std::vector<int>& array, const int char_num, const std::vector<char>& isSmall, const std::vector<int>& bucket, const std::vector<int>& lmsIndices) { // 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; }