给你 'n' 个字符串 w1, w2, ......, wn。令 Si 表示通过考虑字符串 wi 的所有唯一子串而形成的字符串集。子字符串被定义为字符串中一个或多个字符的连续序列。可以在此处找到有关子字符串的更多信息。让'S'= {S1 U S2 U .... Sn}.i.e'S'是一组字符串，通过考虑所有集合S1，S2，..... Sn中的所有唯一字符串而形成。您将获得许多查询，对于每个查询，您将获得一个整数“k”。您的任务是输出集合“S”中按字典序排列的第 k 个最小字符串。
输入:
输入的第一行包含一个整数“n”，表示字符串的数量。接下来的“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)
此错误出现在少数测试用例中。谁能告诉我为什么会出现此错误以及我应该如何纠正此错误？
最佳答案
@enjay 的回答是正确的。我将为任何刚接触此类字符串处理算法问题并想了解更多信息的人详细说明。我的回答将描绘大局并为所提到的任何细节提供指示。
@sachin在interviewstreet.com上指出的问题属于一大类涉及子串、回文等的问题。所有这些问题都可以通过一种专用数据结构来解决:后缀数组(en.wikipedia.org/wiki/Suffix_array)。完整的学习路径如下。但如果你只是在解决问题时受到安慰，你可以直接进入3。
特里 (http://en.wikipedia.org/wiki/Trie)。后缀树的基础。
后缀树 (http://en.wikipedia.org/wiki/Suffix_tree)。将一个字符串的所有后缀放入 Trie 中。请注意，给定字符串的任何子字符串都是给定字符串后缀之一的某个前缀。后缀树的想法很鼓舞人心，但由于后缀树的构造要么太复杂而无法实现要么太慢，在实践中，我怀疑有人使用它。然而，对于任何想要挑战不必要困难的人来说，这里是后缀树构造算法的最佳例证:http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english
后缀数组 (http://en.wikipedia.org/wiki/Suffix_array)。后缀数组包含后缀树所具有的任何信息(因此可以做任何后缀树可以做的事情)并且更容易实现。话虽这么说，如果你想用它完成任何不平凡的事情，你至少需要为 RMQ 构造三个数组和一个索引。三个数组分别是:
一个。后缀数组本身。
排名数组。
高度数组。
由于使用后缀数组时的一个常见任务是找到两个后缀的最长公共(public)前缀，因此需要对高度数组进行RMQ查询。此处描述了 RMQ:http://en.wikipedia.org/wiki/Range_Minimum_Query
关于c++ - InterviewStreet 查找字符串，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/11263479/