InterviewStreet查找字符串
给你'n'个字符串w1，w2，......，wn。 设Si表示通过考虑字符串wi的所有唯一子串形成的字符串集合。 子字符串被定义为字符串中一个或多个字符的连续序列。 有关子字符串的更多信息可以在这里找到。 假设'S'= {S1 U S2 U ... Sn} .ie'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构造至少三个数组和一个索引。 这三个阵列是：
一个。 后缀数组本身。
湾 排名数组。
C。 高度数组。
由于使用后缀数组的一个常见任务是查找两个后缀的最长公共前缀，因此需要对高度数组执行RMQ查询。 这里描述RMQ：http：//en.wikipedia.org/wiki/Range_Minimum_Query
你会得到bad_alloc错误，因为有太多独特的子字符串以适应内存。 为了纠正它，你可以使用任何不需要存储每个唯一子字符串的方法。
我的解决方案非常复杂，所以我只提供算法的草图。
可以仅存储那些在w1，w2，......，wn中的每个可能位置开始并在w1，w2，......，wn的末尾结束的子串。 而不是整个子字符串，您只能存储指向其起始字符的指针。
要回答查询，可以对所有查询进行排序，对所有子字符串进行排序。 然后按照以下方式迭代子字符串：从相同字符开始取所有子字符串，然后将所有子字符串与第二个字符相同，依此类推。 换句话说， 隐含地构造了一个所有内部节点权重为1的树并且所有叶节点的权重等于剩余的唯一子串的长度，对应于此节点。 你迭代这个trie，计算每个节点权重的累计和，并将它与下一个尚未处理的查询进行比较。 只要找到匹配项，就会打印子字符串并继续遍历。
所有这些都不需要太多的内存，但对计算资源非常渴望。 但它可能会被优化。 您可以使用显式的trie来存储所有短子串（可能长度为1 .. 2或1 .. 3）。 您也可以使用桶排序算法对较长的子字符串进行排序。
使用一个后缀数组...它会更快，更容易在内存上genarating所有子串...如果你排序后缀数组，然后尝试搜索使用一些扩展的数据结构，如lcp数组和累积子串数count数组及时解决并在内存限制内......
链接地址: http://www.djcxy.com/p/40101.html