InterviewStreet查找字符串

给出'n'个字符串w1，w2，......，wn。设Si表示通过考虑字符串wi的所有唯一子串形成的字符串集合。子字符串被定义为字符串中一个或多个字符的连续序列。有关子字符串的更多信息可以在这里找到。假设'S'= {S1 U S2 U ... Sn} .i.e'S'是通过考虑所有集合S1，S2，... Sn中的所有唯一字符串而形成的一组字符串。您将收到很多查询，并且对于每个查询，您将得到一个整数'k'。你的任务是从集合'S'中输出字典中第k个最小的字符串。InterviewStreet查找字符串

输入：

输入的第一行包含一个整数“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)

此错误是出现在一些测试用例。有人可以告诉我为什么我得到这个错误，我应该如何纠正这个错误？

来源

2012-06-29 sachin

这意味着你用完堆内存。还没有彻底读完它，但是如果你存储了每一个可能的子串，它看起来像你可能存储了大量字符串的地狱。 – BoBTFish

没错，那么我应该怎么做才能改变方法？ – sachin

一个需要的地方存放这些子（或一组），如果一个人到最后打印从字典有序集合子 – sachin

你得到bad_alloc错误，因为有太多独特的子字符串以适应内存。为了纠正它，你可以使用任何不需要存储每个唯一子字符串的方法。

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

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

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

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

来源

2012-06-29 15:48:47

啊..看起来很复杂:)但仍然thanx。 – sachin

@ gsingh2011：结束于每个可能位置的子字符串不会存储在任何位置。否则，可能没有足够的内存来保存每个子字符串。虽然我们不存储每个子字符串，但我们可以在本文的后半部分解释它们时对它们进行计数。实际上，这里描述的排序子串是[通用后缀数组]（http://en.wikipedia.org/wiki/Suffix_array）。另一种方法是使用[通用后缀树]（http://en.wikipedia.org/wiki/Generalised_suffix_tree）并按照深度优先搜索的顺序对节点进行计数，但它需要更多内存。 –

使用后缀数组 ...这将是更快，更容易的内存比genarating所有子...... 如果u排序的后缀数组，然后尝试使用一些增广的数据结构像的的LCP阵列搜索和cumulative-substring-count数组你可以在时间和内存限制内解决它....

来源

2012-08-10 14:11:38 jemmanuel

@ 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构造至少三个数组和一个索引。这三个阵列是：

a。后缀数组本身。

b。排名数组。

c。高度数组。

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

来源

2013-01-13 02:49:01 luanjunyi

InterviewStreet查找字符串

回答

相关问题