由来:KMP算法只能实现浏览一次目标串匹配一个模式串,而如果需要一次匹配多个模式串(即多模匹配问题),则需要更新原有的算法。
Shift-And算法
KMP算法的升级版:Shift-And算法
Shift-And算法只能实现正则匹配,如模式串长这样的情况:(a|b|c)&(d|e)&f
此时模式串为adf,aef,bdf,bef,cdf,cef,但该算法只能识别存在,不能具体识别存在哪一个
说白了,Shift-And算法可实现浏览一次目标串便能匹配多个模式串,但仅限于模式串之间有一定规律的情况,且不能指出具体识别到了哪个模式串
int shift_and(const char *text, const char *str) {
int code[128] = {0}; //辅助表
int n = 0; //模式串长度
for(int i = 0; str[i]; i++, n++) {
code[str[i]] |= (1 << i); //更新辅助表中的位掩码
}
int ans = 0; //ans的第n位为1代表目前text的n位后缀与str的n位前缀成功匹对
for(int i = 0; text[i]; i++) {
ans = (ans << 1 | 1) & code[text[i]];
if(ans & (1 << (n - 1))) return (i + 1) - n;
}
return -1;
}
AC自动机
Trie树+KMP算法思想:AC自动机
AC自动机可实现浏览一次目标串便能匹配多个模式串,且模式串之间可以毫无规律
类比:
KMP算法在BF算法的基础上增加了next数组
AC自动机在Trie树的基础上增加了fail指针
fail指针的构建:
广搜遍历(需要维护一个队列),第一层结点的fail指针都指向root,第n+1层fail指针的构建方法:站在第n层,沿着fail指针找到该结点下能与自己相匹配的结点赋值给第n+1层的fail指针,若找不到则沿着fail指针的fail指针继续寻找,直到fail指针指向root时,若在root下仍无法找到与自己相匹配的结点,则第n+1层的fail指针指向root。
注:在实际的应用中可采用路径压缩的方法,直接令所有结点下的空结点(即空结点的fail指针)都改为fail指针所指向结点的下一结点,而非空结点的fail指针也同上。这样一来,从第一层开始所有结点的下一结点的指向便都是明确的(第一层的空结点,即root下的空结点仍为root),便不用再反复判断能否匹配的问题。
#define base 26
void initBuildFaildQueue(Node *root, Queue *que) {
root->fail = NULL;
for(int i = 0; i < base; i++) {
if(root->next[i] == NULL) {
root->next[i] = root;
continue;
}
root->next[i]->fail = root;
push(que, root->next[i]);
}
return;
}
void build_fail(Node *root) {
Queue *que = initQueue(node_cnt);
initBuildFaildQueue(root, que);
while(!empty(que)) {
Node *node = front(que);
pop(que);
for(int i = 0; i < base; i++) {
if(node->next[i] == NULL) {
node->next[i] = node->fail->next[i];
continue;
}
node->next[i]->fail = node->fail->next[i];
push(que, node->next[i]);
}
}
clearQueue(que);
return;
}
标签:结点,匹配,多模,next,问题,que,fail,root,指针
From: https://www.cnblogs.com/Kelvin-Wu/p/16795341.html