0

在此处输入图像描述

所以我试图将这个索引（int）和数据（字符串）实现到一个 Dictionary 类中，该类采用上述类型的索引和数据。这是我的代码：

for (int i = 0; i < size; i++){
     dict[i].setIndex(i);
     for (int j = i; j <= size; j++){
          dict[i].data += input[j];
     }
}

此代码适用于 <10KiB 的小文本文件，但当我输入大文本文件时，循环似乎永远运行。它一直运行，直到用完整个内存，然后使 IDE 崩溃。我在这里做错了什么/或者有没有办法优化这个过程？

编辑：这里的大小变量是指 input.length()。

4

1 回答 1

1

因为你试图对后缀进行排序，所以应该使用后缀数组，它旨在有效地解决这个问题。它不是存储后缀本身，而是存储后缀开始的索引。每当您尝试自己存储您将使用的所有 suffices 时O(n^2)，使得此类代码无法在更大的输入上运行。

它对这些指数进行了如下排序。它不是对后缀本身进行排序，而是对字符串的循环旋转进行排序。让我们扩展单词的子字符串含义以使用循环字符串，允许我们在结束位置之后使用起始位置。请注意，任何大小的子字符串2k都可以表示为两个大小的子字符串的串联k。因此，假设我们已经对 size 的所有子字符串进行了排序k，我们可以2k通过对子字符串的每一半进行两次比较来对 size 的子字符串进行排序。O(n log n)因此，如果使用基于比较的排序，或者在这种情况下，甚至在O(n)使用例如计数排序时，可以及时将处理的子字符串长度加倍。对长度为 1 的子串进行排序是微不足道的。

因此，最终的算法将是：对所有大小为 1 的子字符串进行排序。然后，直到您对足够长的字符串进行排序，将排序的子字符串的大小加倍。这种加倍只能重复O(log n)多次，这意味着整个算法在O(n log n)时间上运行并使用O(n)空间。你最终会得到一个 suffices 起始位置的索引数组，按它们所代表的后缀排序。使用这种表示，您可以轻松获取旋转字符串 ( ans[(suffixIndex + n - 1) % n]) 的最后一个字符，或字符串的任何其他部分。

这个页面有更多关于这个算法的细节，并提供了一个 C++ 语言的实现

于 2020-12-17T12:02:54.737 回答