检查一组字符串中是否有匹配输入文本的算法？

Question

因此，我们有一组多个字符串，并希望最优算法检查是否可以在输入文本中找到这些字符串中的任何一个。重要的是，我们对查找所有匹配的字符串不感兴趣，只要找到一个就足够了。

我发现了这一点：http://en.wikipedia.org/wiki/Aho%E2%80%93Corasick_string_matching_algorithm它看起来真的很好，但它能找到所有匹配的模式。如果我们不需要额外的信息，有没有办法更快地得到一些东西？

当然，当Aho Corasick算法找到第一个匹配模式时，我们可以终止它，但perhars是否有另一种方法可以更快地解决这种类型的问题？

Answer 1

你不能降低它，因为它的复杂性是

算法的复杂度是模式长度加上搜索文本的长度加上输出匹配的数量的线性关系。

显然，您必须仔细检查每个模式和文本。

唯一要减少的是输出匹配的数量。但这真的很简单。在原始算法中，一旦满足接受状态，它就会输出与之匹配的所有字典条目。对于您的变体，只需将接受状态标记为接受并输出一些“接受”符号，或者在构造FSM时任意选择一个字典项并输出它。

Answer 2

只需构造一个正则表达式，让您的编程语言的库为您完成繁重的工作和优化。我最近在C#中写道：http://rextester.com/WFQNET2876