在字符串中有效查找任何一组子字符串

假设我们有3个字符串："ab", "cd" and "ef"。
让我们假设我们想要搜索的子串是上述字符串的排列，
即any of {"abcdef","abefcd","efabcd","efcdab","cdefab","cdabcf"}
现在让我们假设我们有一个很长的字符串，我们想从上面的集合中找到任何一个子字符串（简化案例并假设主串中只有一个子串出现一次）。
例如。在字符串中有效查找任何一组子字符串

Main string: abcdghefcdabgh 
Substring:   efcdab

这种情况下搜索的最有效方法是什么？使用暴力和搜索每个可能的子字符串是非常低效的。
Rabin-Karp进行多重模式搜索是我想到的一种方法。不过，我不确定在这种情况下会有一个非常有效的散列函数。

来源

2011-11-01 eku

有什么问题由[百科]中描述的拉宾，卡普滚动散列（http://en.wikipedia.org/wiki/ Rolling_hash）？ –

对于您描述的特定情况，检查所需长度的搜索字符串的每个子字符串（对于搜索字符串长度为n的搜索字符串有O（n））似乎并不是很有效，并查看它是否是目标串。如果目标字符串集合很小，可以在O（m）（其中m是目标字符串的数量）中构建一个哈希表...否则，你可以构造某种搜索树或其他东西。我不知道你怎么认为你可以做得比O（n + m）更好......如果这件事失去了一些显而易见的事情，那么抱歉我会变得密集。 – Patrick87

@robmayoff很好，它没有错。我只想知道是否有更好的方法，我错过了:) – eku

搜索任何“ab”，在+1或-1处查找“cd”或“ef”，继续查找整个排列。

例如：使用

"ab", "cd", "ef"
在"asjkdnjdnaboidnabefcdasdnmk"

的"ab"一审是在9，即：

lowerFound = 9 
upperfound = 11 \\ found index + length of found string

从那里，你知道，在置换任何其他比赛有要么在lowerfound之前，要么在upperfound之上，因此在两侧看，为此例如：
dn ab oi不包含任何匹配，从而放弃和寻找下一个"ab"在15

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

我已经制定了计划，以做到这一点，但它是相当大的，行明智的，所以我已经把请随时批评这种做法。
要减少最坏情况"ababababababababcdef"您可能希望保持索引已在内存中搜索。

来源

2011-11-01 05:08:29 Serdalis

我不确定查找模式字符串的所有排列是否是一个选项，但是如果可以在合理的时间内找到这些排列，那么您可以使用此算法来同时检查所有模式。

http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm

，这将需要一些额外的空间，另一种较快的方法，将构建在文本上后缀树。然后匹配每个模式。制作树是O（n），其中n是文本大小。匹配每个模式是O（p）其中p是每个模式的长度。

总时间= O（P1 + P2 + P3 ... + N）

来源

2011-11-01 08:11:52 Sushant

在字符串中有效查找任何一组子字符串

回答

相关问题