线性模式匹配算法？

Question

我有一个零和一的线性列表，我需要匹配多个简单模式并找到第一个出现的地方。例如，我可能需要在长度为 800 万的列表中查找 0001101101、01010100100 或 10100100010。我只需要找到其中任何一个的第一次出现，然后返回它出现的索引。但是，在大列表上进行循环和访问可能代价高昂，我宁愿不要这样做太多次。

有没有比做更快的方法

foreach (patterns) {
    for (i=0; i < listLength; i++)
        for(t=0; t < patternlength; t++)
            if( list[i+t] != pattern[t] ) {
                 break;
            }
            if( t == patternlength - 1 ) {
                 return i;  // pattern found!
            }
        }
    }
}

编辑: 顺便说一句，我已经根据上面的伪代码实现了这个程序，性能还可以，但没什么了不起的。我估计我在处理器的单个内核上每秒处理大约 600 万位。我正在使用它进行图像处理，它必须处理几千个 8 兆像素的图像，所以一点点帮助。

编辑: 如果不清楚，我正在使用位数组，所以只有两种可能性:ONE 和 ZERO。它是用 C++ 编写的。

编辑:感谢 BM 和 KMP 算法的指点。我注意到，在 BM 的维基百科页面上，它说

The algorithm preprocesses the target string (key) that is being searched for, but not the string being searched in (unlike some algorithms that preprocess the string to be searched and can then amortize the expense of the preprocessing by searching repeatedly).

这看起来很有趣，但它没有给出此类算法的任何示例。这样的事情也有帮助吗？

Answer 1

谷歌搜索的关键是“多模式”字符串匹配。

回到 1975 年，Aho and Corasick发布了一个(线性时间)算法，用于 fgrep 的原始版本。该算法随后得到了许多研究人员的改进。例如，Commentz-Walter (1979)结合 Aho&Corasick 与 Boyer&Moore匹配。 Baeza-Yates (1989)将 AC 与 Boyer-Moore-Horspool 组合在一起变种。 Wu and Manber (1994)做了类似的工作。

多模式匹配算法的AC线的替代是Rabin and Karp's算法。

我建议先阅读 Aho-Corasick 和 Rabin-Karp 维基百科页面，然后再决定这对您的情况是否有意义。如果是这样，也许已经有适用于您的语言/运行时的实现。