高效地查找字符串中一组子字符串中的任何一个
假设我们有3个字符串："ab", "cd" and "ef"。
让我们假设我们想要搜索的子串是上述串的排列，
即any of {"abcdef","abefcd","efabcd","efcdab","cdefab","cdabcf"}
现在让我们假设我们有一个很长的字符串，并且我们想要在其中找到上面集合中的任何一个子字符串(稍微简化一下情况，假设在主字符串中只有一个子字符串出现一次)。
例如：
Main string: abcdghefcdabgh
Substring: efcdab在这种情况下，最有效的搜索方式是什么？使用暴力并搜索每个可能的子字符串是非常低效的。
Rabin-Karp的多模式搜索是我想到的一种方法。然而，我不确定在这种情况下，一个非常有效的哈希函数是什么。
回答 2
Stack Overflow用户
发布于 2011-11-01 05:08:29
搜索任何"ab"，在+1或-1处找到"cd“或"ef”，继续直到找到整个排列。
示例：
使用"ab", "cd", "ef"
在"asjkdnjdnaboidnabefcdasdnmk"中
9是"ab"的第一个实例，因此：
lowerFound = 9
upperfound = 11 \\ found index + length of found string从那里你知道排列中的任何其他匹配必须在lowerfound之前或upperfound之上，因此查看两边，对于这个例子：
dn ab oi不包含任何匹配项，因此将丢弃并在15处查找下一个"ab"
lowerFound = 15
upperfound = 17
search for "cd" or "ef" at 15-length or 17
found "ab"+"ef"
lowerFound = 15
upperfound = 19
search for "cd" at 15-length or 19
found "abef"+"cd"
return我已经制定了一个程序来做到这一点，但它是相当大的，行明智的，所以我把它放在right here，请随时批评这种方法。
为了减少最坏情况下的"ababababababababcdef"，您可能希望将已搜索到的索引保留在内存中。
Stack Overflow用户
发布于 2011-11-01 08:11:53
我不确定是否可以找到模式字符串的所有排列，但如果可以在合理的时间内找到这些排列，那么您可以使用此算法来同时检查所有模式。
http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm
另一种更快的方法需要一些额外的空间，那就是在文本上构建后缀树。然后对每个模式进行匹配。生成树是O(n)，其中n是文本大小。匹配每个模式是O(p)，其中p是每个模式的长度。
总时间= O( p1 + p2 + p3...+n)
https://stackoverflow.com/questions/7962479
复制相似问题
腾讯云开发者
