如何有效地搜索數組中的特定序列？

我正在尋找特定序列的大陣列，我覺得我正在用蠻力而不是電腦來解決問題科學。如何有效地搜索數組中的特定序列？

目前，我正在順序查找搜索序列中第一個項目的大數組，然後檢查每個項目，直到失敗或完全匹配。這提供了100％的準確度，但對於大型陣列來說速度並不快。

我從來都不是計算機科學的學生，所以我錯過了許多算法類，這裏有很多人可能有。有沒有更好的方法來搜索數組中的序列？如果它有所作爲，我不一定對完美的準確性感興趣。

2012-02-19 Nick

數組是否處於某種排序順序？你在數組中尋找什麼？順序是最好的，你可以做一個未排序的數組，但如果它被排序，我們可以做得更好。 – Jordan 2012-02-19 06:17:29

@Jordan這不是可排序的數據。假定任意的順序。 – Nick 2012-02-19 06:21:03

我一直很喜歡KMP算法。 – davin 2012-02-19 06:21:58

如何使用Boyer-Moore algorithm？這非常簡單直接，並且可以提高實際速度，尤其是在目標序列相當長的情況下。它的意思是搜索字符串，但這只是一個特定類型的數組。

2012-02-19 06:19:21 Janne

除非我誤解，否則不會減少順序橫向陣列的需求。這將減少一個元素上的檢查數量來丟棄它。這是一個有用的優化，但最終OP將需要對數組進行順序搜索，因爲它是未排序的。只是澄清。 – Jordan 2012-02-19 06:42:30

喬丹絕對只是一個不斷增加的因素。但是，如果目標序列很長，它仍然意味着在實踐中有很大的改進;在跑步時間上改善五倍或什麼都不是打噴嚏。正如你在下面所說的，只要他不能構造他的數據，就沒有其他的事情要做了。 – Janne 2012-02-19 07:21:26

是的，我同意，這就是爲什麼我爲你+1。我只是更想澄清OP，因爲他表示他沒有CS背景，因爲他的問題的性質導致了什麼好處以及他無法獲得什麼好處。 – Jordan 2012-02-19 08:10:25

有沒有更好的方法來搜索陣列本身的比賽候選人。如果你沒有命令，你不能在不考慮候選人的情況下丟棄候選人。

這就是說你可以使用Janne建議的方法優化候選人的接受或拒絕。

2012-02-19 06:44:39 Jordan

如果您需要在相同的順序來搜索很多模式可以使用suffix arrays

如果你必須尋找一個模式，那麼你可以提高多一點與博耶 - 摩爾或克努特 - Morris-蠻力Pratt

2012-02-20 00:31:35

回答