string - 有效地查找字符串中的一组子字符串中的任何一个

Question

假设我们有 3 个字符串:"ab"、"cd"和 "ef"。
假设我们要搜索的子字符串是上述字符串的排列，
即 {"abcdef","abefcd","efabcd","efcdab","cdefab","cdabcf”
现在让我们假设我们有一个长字符串，我们想从上面的集合中找到任何一个子字符串(稍微简化一下，假设主字符串中只有一个子字符串出现一次).
例如。

Main string: abcdghefcdabgh
Substring:         efcdab

在这种情况下，进行搜索的最有效方法是什么？进行蛮力搜索每个可能的子串是非常低效的。
用于多模式搜索的 Rabin-Karp 是我想到的一种方法。但是我不确定在那种情况下会是一个非常有效的哈希函数。

Answer 1

搜索任何“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 不包含任何匹配项，因此丢弃并在 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"，您可能希望在内存中保留已搜索的索引。