如何有效地搜索数组中的特定序列？

我正在寻找特定序列的大阵列，我觉得我正在用蛮力而不是电脑来解决问题科学。如何有效地搜索数组中的特定序列？

目前，我正在顺序查找搜索序列中第一个项目的大数组，然后检查每个项目，直到失败或完全匹配。这提供了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

回答