输入：一个字符串数组和一个字符串。
任务：查找数组中条目的任何子字符串与输入字符串匹配的所有条目。
输入数组可以以任何所需的方式准备或排序，并可以构建所需的任何辅助数据结构。准备数据结构所需的时间（在理智范围内）并不重要。
目标是搜索的最大速度。
您会使用什么算法，而不仅仅是线性搜索？
问问题
77 次
2 回答
0
您可能想要建立所有字符串后缀的索引。查看后缀树以了解如何做到这一点。维基百科的文章可能过于笼统，所以这里是一个改编的算法：
建筑指数
- 对于数组中的每个字符串
- 获取其所有后缀（长度为 N 的字符串有 N 个后缀）并将对字符串的引用存储在有序关联容器中（OrderedMap> (index)
搜索
- 在索引中找到搜索词的下限
- 从下限开始移动索引，直到索引键不会停止以搜索词为前缀
- 您将找到的所有参考文献的总和就是您的搜索结果
长度为 N 但只有 N 个后缀的字符串有 N²/2 个子字符串。因此，基于后缀的数据结构应该比基于子字符串的内存更有效。
于 2013-10-17T02:30:38.180 回答
0
因为它说准备数据结构所需的时间并不重要，所以我会散列它。键是字符串（特别是子字符串），值是与数组中的索引相对应的整数列表，其元素以键作为子字符串。
要构建，获取数组中的每个字符串并确定该字符串的所有可能子字符串，将每个这样的键值对插入到哈希表中。如果键已经存在，则将索引附加到列表中，而不是插入/创建新列表。
一旦你建立了这个哈希表，它就像 O(1) 根据输入字符串抓取列表并返回一样简单。
编辑：更仔细地查看这个问题，您似乎想要返回数组中的实际字符串，而不是它们的索引。哈希表方法将适用于任何一种方式。
于 2013-10-17T01:57:02.937 回答