给定一组字符串和一组子字符串作为不同的数组。如何从每个数组中找到正确的匹配值？
给定一组字符串和一组子字符串作为不同的数组。如何从每个数组中找到正确的匹配值？
提问于 2019-01-24 10:33:38
设A=“堆栈”、“溢出”、“算法”、B= "gor“、"tac”、"flo“。A和B是字符串数组，其中B有子字符串。
保证B中的每个字符串都是A中只有一个字符串的子字符串，而A中的每个字符串在B中只有一个匹配项。还考虑到A和B中的字符串数相等。
输出B，这样Bi应该是Ai的子字符串。
上述示例的输出如下：
B= "tac“、"flo”、"gor“。
我只能想到天真的方法。我们有更好的解决上述问题的办法吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2019-01-24 11:09:16
将所有字符串连接到长度为s的超字符串L=sum(len(i))中，存储字符串开始的索引。
为超级字符串(LlogL)构建后缀数组
搜索后缀数组(N*logL)中的每个子字符串
获取与此索引对应的字符串
如果子字符串不能在找到的位置和下一个字符串的索引之间匹配，请使用另一个后缀(比如fax/emotion/axel和搜索axe)。
Stack Overflow用户
发布于 2019-01-24 11:04:59
我想，通过天真的方法，您的意思是对B中的每个子字符串，通过A中的所有单词来查找匹配项。该方法具有O(n^2)的复杂性
但是，您也可以尝试使用子串指数索引A中的单词。构建此索引通常需要O(n * log n)构造时间。
之后，您可以有效地利用这个索引(通常是O(log ))查找包含子字符串的单词。因此，对B中的每个子字符串执行此操作的是O(n * log )
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/54344562
复制相关文章
相似问题
腾讯云开发者
