针对预定义种子列表(不区分大小写)进行字符串测试的最快C++算法
我有种子字符串的列表，大约100个预定义的字符串。所有字符串仅包含ASCII字符。
std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"};我的应用程序经常收到很多字符串，它们可以包含任何字符。我需要检查收到的每一行，并决定它是否包含任何种子。比较必须不区分大小写。
我需要最快的算法来测试接收到的字符串。
现在我的应用使用这个算法：
std::wstring testedStr;
for (auto & seed : seeds)
{
if (boost::icontains(testedStr, seed))
{
return true;
}
}
return false;它工作得很好，但我不确定这是不是最有效的方法。
为了获得更好的性能，如何实现该算法？
这是一个Windows应用程序。应用程序接收有效的std::wstring字符串。
更新
为此，我实现了Aho-Corasick算法。如果有人能审查我的代码，那就太好了--我对这样的算法没有太多的经验。链接到实现：gist.github.com
回答 7
Stack Overflow用户
发布于 2016-05-29 20:03:18
它构建trie/自动机，其中一些顶点被标记为终端，这意味着字符串具有种子。
它是用O(sum of dictionary word lengths)构建的，并用O(test string length)给出了答案
优势：
- 算法并不难实现(至少与后缀结构相比)
算法并不难实现(至少与后缀结构相比)
如果它是ASCII，你可以通过降低每个符号来使其不区分大小写(非ASCII字符无论如何都不匹配)
Stack Overflow用户
发布于 2016-05-29 20:06:16
如果有有限数量的匹配字符串，这意味着您可以构建一棵树，这样，从根到叶，相似的字符串将占据相似的分支。
这也称为, or Radix Tree。
例如，我们可能有字符串cat, coach, con, conch和dark, dad, dank, do。它们的trie可能如下所示：
搜索树中的一个单词将从根开始搜索树。把它放到一片叶子上就相当于一颗种子的匹配。无论如何，字符串中的每个字符都应该与它们的一个子项匹配。如果没有，你可以终止搜索(例如，你不会考虑任何以"g“开头的单词或任何以”cu“开头的单词)。
有各种各样的算法来构建树，搜索它，以及动态地修改它，但我想我应该给出一个概念性的解决方案概述，而不是一个具体的解决方案，因为我不知道最好的算法。
从概念上讲，您可能用来搜索树的算法与基数排序背后的思想有关，基数排序是字符串中的字符在给定时间点可能具有的固定数量的类别或值。
这让你可以根据你的word-list检查一个单词。由于您要将此单词列表作为输入字符串的子字符串进行查找，因此将会有更多内容。
编辑：正如其他答案所提到的，用于字符串匹配的阿霍-科拉西克算法是一种用于执行字符串匹配的复杂算法，它由一个带有附加链接的trie组成，用于在树中使用“快捷方式”，并具有不同的搜索模式。(有趣的是，Alfred Aho也是流行的编译器教科书“编译器:原理、技术和工具”以及算法教科书“计算机算法的设计和分析”的撰稿人。他也是贝尔实验室的前成员。玛格丽特·J·科拉西克似乎没有太多关于自己的公开信息。)
Stack Overflow用户
发布于 2016-05-29 21:26:19
你应该尝试一个预先存在的regex实用程序，它可能比你的手摇算法慢，但regex是关于匹配多种可能性的，所以它很可能已经比hashmap或简单地比较所有字符串快了好几倍。我相信正则表达式实现可能已经使用了RiaD提到的Aho-Corasick算法，所以基本上您将拥有一个经过良好测试且快速的实现。
如果您有C++11，那么您就已经有了一个标准的regex库
#include <string>
#include <regex>
int main(){
std::regex self_regex("google|yahoo|stackoverflow");
regex_match(input_string ,self_regex);
}我希望它能生成最佳的最小匹配树，所以我希望它真的很快(而且可靠！)
https://stackoverflow.com/questions/37509461
复制相似问题
腾讯云开发者
