字符串匹配算法.pdf - 墨天轮文档

字符串匹配算法.pdf

6页

0次

2024-03-25

免费下载

字符串匹配算法（AC 自动机 Aho-Corasick）

1. 多模式串匹配

 前面学的 BF、RK、BM、KMP 都是单模式串匹配算法（一个模式串，一个主串）

 多模式串匹配，即在一个主串中查找多个模式串（Trie 树是多模式匹配）

 比如实现多个敏感词过滤；单模式需要一遍遍的，扫描，过滤，扫描，过滤；多模式扫描一遍，过滤完成

2. 经典多模式串匹配–AC 自动机

AC 自动机算法（Aho-Corasick 算法），是在 Trie 树之上，加了类似 KMP 的 next 数组。

class ACNode //AC 自动机的 Trie 树节点类,假设只有 26 个字母的数据集{public:

char data;

ACNode *children[charNum];

size_t count; //

记录这个节点被多少个单词占用

bool isEndOfWord;//是否是一个单词的结束字符

size_t freq; //单词插入的频次

int length; //当 isEndOFWord 为 True 时，记录模式串长度

ACNode *fail; //失败指针

ACNode(char ch = '/'):data(ch), isEndOfWord(false),

count(0), freq(0),length(-1),fail(NULL)

{

memset(children,0,sizeof(ACNode*) * charNum);

}

~ACNode(){}};

复制

2.1 AC 自动机构建

 1，将多个模式串插入 Trie 树。

 2，在 Trie 树上构建失败指针（相当于 KMP 中的失效函数 next 数组）

在这里插入图片描述

of 6

免费下载

关注