Radix-Tree:C + +模块使用字典为确定性有限自动机状态实现基数树

Radix Trie（有时称为Trie，数字树或前缀树）是树形的确定性自动机（DFA）。 这是一种serach trie，用于存储动态集或关联数组，其中键通常是字符串。 与二进制搜索不同，树中没有与特定关键字关联的节点。 相反，它的行为更像是状态机，您的当前值就是您在状态内所处的位置。 在确定有限的语言时，尝试遍历比遍历每种语言要有效得多。 例如，在英语中，有数百万个单词。 但是，只有26个字母。 每个单词都必须以字母开头。 因此，与其进行一百万次比较以查看单词是否与语言匹配，我们最多可以对第一个字母进行26次比较，然后对第二个字母进行比较，然后对第三个字母进行比较。 在此示例中，我们将字母存储在哈希中，因此有恒定的查找时间。 因此，将字母与语言匹配所需的最大时间仅进行n次迭代，其中n是字符串的长度。 入门 在src目录中运行make来创建您的二进制文件。 运行程序。 输入 查看ex