c++ - C++ 中的高效字符串/模式匹配(后缀数组、特里树、后缀树？)

Question

我正在寻找一种高效的数据结构来对非常庞大的字符串集进行字符串/模式匹配。我发现了有关尝试、后缀树和后缀数组的信息。但是到目前为止，我还没有找到一个现成的 C/C++ 实现(我自己实现它似乎很困难而且容易出错)。但我仍然不确定后缀数组是否真的是我要找的东西......我已经尝试过 libdivsufsort 和 esaxx，但找不到如何使用它们来满足我的需要:

我想使用一组预定义的字符串，使用通配符(甚至正则表达式)来匹配用户输入。我得到了一个巨大的预定义字符串列表，即

“什么是*？”“什么是 XYZ？”“多少钱 *？”...

现在我想找到最匹配的字符串(如果有的话，完全匹配)。IE。用户输入:>XYZ 是什么？应该找到“什么是 XYZ？”而不是“什么是*？”，而是“什么是什么？”应该找到“WHAT IS *?” (假设 * 是任意字符数的通配符)。

构建结构的时间要求不高(而且结构不必非常节省空间)，但搜索时间不应太长。这怎么可能轻易做到？欢迎使用任何框架/库或代码示例

谢谢

Answer 1

根据您的评论，模式不需要在运行时更新，我不确定您是否需要运行时结构。

我建议使用 re2c或 ragel将模式编译为将进行模式匹配的代码。