3

给你 'n' 个字符串 w1, w2, ......, wn。令 Si 表示通过考虑字符串 wi 的所有唯一子字符串形成的字符串集合。子字符串定义为字符串中一个或多个字符的连续序列。可以在此处找到有关子字符串的更多信息。让'S' = {S1 U S2 U .... Sn}。即'S'是通过考虑所有集合S1，S2，......Sn中的所有唯一字符串而形成的字符串集合。您将获得许多查询，并且对于每个查询，您将获得一个整数“k”。您的任务是从集合“S”中输出按字典顺序排列的第 k 个最小字符串。

输入：

输入的第一行包含一个整数“n”，表示字符串的数量。接下来的每一行都由一个字符串组成。第 i 行 (1<=i<=n) 上的字符串用 wi 表示，长度为 mi。下一行由一个整数“q”组成，表示查询的数量。接下来的“q”行中的每一行都包含一个整数“k”。

注意：输入字符串仅由小写英文字母 'a' - 'z' 组成。

输出：

输出“q”行，其中第 i 行由一个字符串组成，该字符串是第 i 个查询的答案。如果输入无效（'k' > |S|），则输出“INVALID”（为清楚起见，引号）。

约束：

1<=n<=50
1<=mi<=2000
1<=q<=500
1<=k<=1000000000

https://www.interviewstreet.com/challenges/dashboard/#problem/4efa210eb70ac

我的方法

对于每个输入字符串，生成其子字符串并将它们添加到集合中，这将自动消除重复并保持它们的排序。返回集合中索引 i 处的元素。

我在这里写了关于上述方法的代码：

http://justprogrammng.blogspot.com/2012/06/interviewstreet-find-strings-solution-c.html

但我面临的问题是

terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)

此错误出现在少数测试用例中。有人可以告诉我为什么我会收到这个错误，我应该如何纠正这个错误？

4

3 回答 3

3

@enjay 的回答是正确的。我将为任何不熟悉此类字符串处理算法问题并想了解更多信息的人详细说明。我的回答将描绘大图并指出所提到的任何细节。

@sachin 在 interviewstreet.com 中指出的问题属于一大群涉及子串、回文等的问题。所有这些问题都可以通过一个专用的数据结构来解决：后缀数组（en.wikipedia.org/wiki/Suffix_array）。完整的学习路径如下。但如果你只是在解决问题，你可以直接进入3。

  1. 特里（http://en.wikipedia.org/wiki/Trie）。后缀树的基础。

  2. 后缀树（http://en.wikipedia.org/wiki/Suffix_tree）。将一个字符串的所有后缀放入 Trie 中。观察给定字符串的任何子字符串是给定字符串后缀之一的某个前缀。后缀树的想法很鼓舞人心，但由于后缀树的构建要么太复杂而无法实现，要么太慢，在实践中，我怀疑有人使用它。但是，对于任何想挑战不必要的困难的人，这里是后缀树构造算法的最佳说明：http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english

  3. 后缀数组（http://en.wikipedia.org/wiki/Suffix_array）。后缀数组包含后缀树所具有的任何信息（因此可以做任何后缀树可以做的事情）并且更容易实现。话虽如此，如果你想用它完成任何不平凡的事情，你需要为 RMQ 构造至少三个数组和一个索引。这三个数组是：

一个。后缀数组本身。

湾。秩数组。

C。高度数组。

由于使用后缀数组时的一项常见任务是查找两个后缀的最长公共前缀，因此需要对高度数组进行 RMQ 查询。RMQ 在这里描述：http ://en.wikipedia.org/wiki/Range_Minimum_Query

于 2013-01-13T02:49:01.720 回答
2

您会收到 bad_alloc 错误，因为有太多唯一的子字符串无法放入内存。要纠正它，您可以使用任何不需要存储每个唯一子字符串的方法。

我的解决方案相当复杂，所以我只提供一个算法草图。

可以只存储那些从 w1、w2、......、wn 中的每个可能位置开始并在 w1、w2、......、wn 结束处结束的子字符串。而不是整个子字符串，您只能存储指向其起始字符的指针。

要回答查询，您可以对所有查询进行排序，对所有子字符串进行排序。然后以以下方式迭代子字符串：取所有从同一个字符开始的子字符串，然后取所有具有相同第二个字符的子字符串，依此类推。换句话说，您隐式构造了一个 trie，其中所有内部节点的权重为 1，所有叶节点的权重等于与该节点相对应的剩余唯一子串的长度。然后您遍历这个 trie，计算每个节点权重的累积总和，并将其与下一个尚未处理的查询进行比较。一旦找到匹配项，就打印子字符串并继续进行 trie 遍历。

所有这些都不需要太多内存，但非常需要计算资源。但它可能会被优化。您可以使用显式 trie 存储所有短子字符串（可能长度为 1 .. 2 或 1 .. 3）。您也可以使用桶排序算法对较长的子字符串进行排序。

于 2012-06-29T15:48:47.170 回答
2

使用后缀数组...它在内存上会比生成所有子字符串更快、更容易...如果您对后缀数组进行排序，然后尝试使用一些扩充数据结构（如lcp 数组和累积子字符串计数数组）进行搜索，您可以在内存限制内及时解决它....

于 2012-08-10T14:11:38.347 回答