针对预定义种子列表进行stringtesting的最快C ++algorithm（不区分大小写）
我有种子string列表，约100个预定义的string。 所有的string只包含ASCII字符。
std::list<std::wstring> seeds{ L"google", L"yahoo", L"stackoverflow"}; 我的应用程序不断收到很多可以包含任何字符的string。 我需要检查每个收到的行，并决定是否包含任何种子。 比较必须不区分大小写。
我需要最快的algorithm来testing收到的string。
现在我的应用程序使用这个algorithm：
std::wstring testedStr; for (auto & seed : seeds) { if (boost::icontains(testedStr, seed)) { return true; } } return false;
它运作良好，但我不确定这是最有效的方法。
为了实现更好的性能，如何实现algorithm？
这是一个Windows应用程序。 应用程序接收有效的std::wstringstring。
更新
为了这个任务，我实施了Aho-Corasickalgorithm。 如果有人可以查看我的代码，那就太好了 – 我对这样的algorithm没有太大的经验。 链接到实施： gist.github.com
你可以使用Aho-Corasickalgorithm
它build立了一些标记为terminal的顶点，这意味着string有种子的自动机。
它build立在O(sum of dictionary word lengths)并在O(test string length)给出答案
优点：
- 它是专门与几个字典的单词和检查时间不依赖于字数（如果我们不考虑它不适合内存等情况下）
- 该algorithm不难实现（至less与后缀结构相比）
如果是ASCII码，则可以通过降低每个符号来使其不区分大小写（非ASCII字符不匹配）
如果匹配string的数量是有限的，这意味着你可以构造一棵树，从根到叶读取类似的string将占据相似的分支。
这也被称为树，或基数树 。
例如，我们可能有cat, coach, con, conch以及dark, dad, dank, do 。 他们的看法可能是这样的：
search树中的一个单词将从根开始search树。 使它成为一片叶子，将对应于一个种子的匹配。 无论如何，string中的每个字符都应该和他们的一个孩子相匹配。 如果没有，可以终止search（例如，你不会考虑任何以“g”开头的单词或以“cu”开头的任何单词）。
有不同的algorithm来构build树，以及search和修改它，但我想我会提供一个解决scheme的概念性概述，而不是一个具体的，因为我不知道最好的algorithm它。
从概念上讲，你可能用来search树的algorithm将与基数固定数量的类别或值在string中的字符可能在给定的时间点上采取的想法有关。
这可以让你检查一个单词对你的单词列表 。 既然你正在寻找这个单词列表作为你的inputstring的子string，那么会比这更多。
编辑：正如其他答案已经提到的，string匹配的Aho-Corasickalgorithm是一个复杂的algorithm来执行string匹配，包括一个额外的链接，以通过树“快捷方式”，并有一个不同的search模式伴随着这一点。 （作为一个有趣的笔记，Alfred Aho也是stream行编译器教科书Compilers：Principles，Techniques，and Tools以及algorithm教科书计算机algorithmdevise和分析的贡献者，他也是Bell实验室，玛格丽特·科拉斯克（Margaret J. Corasick）似乎没有太多公开的信息。）
您应该尝试一个预先存在的正则expression式实用程序，它可能比您的手动滚动algorithm慢，但是正则expression式匹配多个可能性，所以它可能已经比散列图或者所有string的简单比较快了几倍。 我相信正则expression式的实现可能已经使用了RiaD提到的Aho-Corasickalgorithm，所以基本上你将有一个经过良好testing和快速实现。
如果你有C ++ 11，你已经有了一个标准的正则expression式库
#include <string> #include <regex> int main(){ std::regex self_regex("google|yahoo|stackoverflow"); regex_match(input_string ,self_regex); }
我期望这会产生最好的最小匹配树，所以我期望它非常快（可靠！）
更快的方法之一是使用后缀树https://en.wikipedia.org/wiki/Suffix_tree ，但这种方法有巨大的缺点 – 难以构build的数据结构是困难的。 该algorithm允许从线性复杂度的string构build树https://en.m.wikipedia.org/wiki/Ukkonen%27s_algorithm
编辑：正如Matthieu M.指出的那样，OP询问一个string是否包含关键字。 我的答案只有当string等于关键字，或如果你可以拆分string，例如空格字符。
特别是有大量的可能的候选人，并且在编译时使用像gperf这样的工具使用完美的哈希函数来了解它们是值得一试的。 主要原则是，你用你的种子生成一个生成器，并且生成一个函数，该函数包含一个对于所有种子值都没有冲突的哈希函数。 在运行时你给这个函数一个string，它计算散列，然后检查它是否是对应于散列值的唯一可能的候选者。
运行时间成本对string进行散列处理，然后与唯一可能的候选对象（种子大小为O（1），string长度为O（1））进行比较。
为了不区分大小写，只需在种子和string上使用tolower即可。
由于string数量不大（〜100），可以使用下一个algorithm：
- 计算你的单词的最大长度。 让它成为N.
- 创build
int checks[N];校验和数组。 - 我们的校验和将是search词组中的所有字符的总和。 所以，你可以为你的列表中的每个单词（编译时已知的）计算这样的校验和，并创build
std::map<int, std::vector<std::wstring>>，其中int是string的校验和，并且vector应该包含你所有的string和校验和。 为每个长度创build这样的映射数组（最多N个），也可以在编译时完成。 - 现在通过指针移动大string。 当指针指向X字符时，应该为所有的
checks整数加上X char的值，并且为每个checks整数（从1到N的数字）移除（XK）字符的值，其中K是checks数组中的整数。 所以，你将永远有正确的校验和存储在checks数组中的所有长度。 之后，在地图上search是否存在这样的对（长度和校验和）的string，如果存在 – 比较它。
它应该给出假阳性结果（当校验和长度相等时，但是短语不是）非常罕见。
所以，我们说R是大串的长度。 然后循环它将采取O（R）。 每一步你将用“+”小号（char值）执行N次操作，N次操作用“ – ”小号（char值），这是非常快的。 每一步你将不得不在checks数组中searchcounter，那就是O（1），因为它是一个内存块。
同样，每一步你将不得不在映射数组中find映射，这也将是O（1），因为它也是一个内存块。 在内部地图中，你将不得不search具有正确校验和的stringlog（F），其中F是地图的大小，它通常不会包含2-3个以上的string，所以我们通常可以假设它也是O （1）。
你也可以检查一下，如果没有相同校验和的string（应该只有100个单词的话就会发生），你可以丢弃地图，存储地图而不是地图。
所以，最后应该给出O（R），这个O很小。这种计算checksum方法是可以改变的，但是这个方法很简单，而且完全快速，而且还有很less的假阳性反应。
作为DarioOO答案的一个变体，通过为你的string编码一个lexparsing器 ，你可以得到一个更快的正则expression式匹配的实现。 虽然通常与yacc一起使用，但这是lex本身可以完成的工作，而lexparsing器通常非常有效。
如果所有的string都很长，那么这种方法可能会下降，因为那样的话，像Aho-Corasick ， Commentz-Walter或Rabin-Karp这样的algorithm可能会提供显着的改进，我怀疑lex实现使用任何这样的algorithm。
如果你必须能够configurationstring而不需要重新configuration，这种方法就更困难了，但是由于flex是开源的，你可以调用它的代码。
