c++ - InterviewStreet查找字符串

系统会为您提供n个字符串w1，w2，......，wn。令Si表示通过考虑字符串wi的所有唯一子字符串形成的字符串集合。子字符串定义为字符串中一个或多个字符的连续序列。有关子字符串的更多信息，请参见此处。令“S” ＝ {S 1 U S2 U .... Sn}。即，“S”是通过考虑所有集合S 1，S 2，.... Sn中的所有唯一字符串形成的一组字符串。您将获得许多查询，并且对于每个查询，您将获得一个整数“k”。您的任务是从集合'S'中输出按字典顺序排列的第k个最小字符串。

输入:

输入的第一行包含单个整数'n'，表示字符串的数量。接下来的'n'行中的每一行都由一个字符串组成。第i行(1
注意:输入字符串仅包含小写英文字母'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

我的方法

对于每个输入字符串，生成其子字符串并将其添加到集合中，这将自动消除重复项并使它们保持排序。返回set中索引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在专访中指出的问题属于涉及子串，回文等的一大类问题。所有这些问题都可以通过一种专用的数据结构来解决:后缀数组(en.wikipedia.org/wiki/Suffix_array)。完整的学习路径如下。但是，如果只考虑解决问题，则可以直接转到3。

Trie(http://en.wikipedia.org/wiki/Trie)。后缀树的基础。

后缀树(http://en.wikipedia.org/wiki/后缀树)。将一个字符串的所有后缀放入Trie。请注意，给定字符串的任何子字符串都是给定字符串后缀之一的前缀。后缀树的想法令人鼓舞，但是由于后缀树的构造太复杂而难以实现或太慢，因此在实践中，我怀疑有人会使用它。但是，对于任何想挑战不必要难度的人，这里都是后缀树的构造算法的最佳说明:http://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english

后缀数组(http://en.wikipedia.org/wiki/Suffix_array)。后缀数组包含后缀树具有的任何信息(因此可以执行后缀树可以执行的任何操作)，并且易于实现。话虽如此，如果您想用它完成不平凡的事情，则需要为RMQ构造至少三个数组和一个索引。这三个数组是:

一种。后缀数组本身。

b。等级数组。

C。高度数组。

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