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

假設我們有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

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

回答

相關問題