首页 > 其他分享 >多模匹配问题

多模匹配问题

时间:2022-10-15 23:22:21浏览次数:55  
标签:结点 匹配 多模 next 问题 que fail root 指针

由来: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

相关文章

  • 如何解决Navicat连接Mysql数据库时出现1251报错问题
    如何解决Navicat连接Mysql数据库时出现1251报错问题​​一、前言​​​​二、错误信息​​​​三、分析问题​​​​四、解决方法​​一、前言二、错误信息  用Navicat软......
  • while循环条件不成立却无法跳出死循环的问题
    在进入循环的时候,实际上是将A从内存加载到寄存器里面运行的,在整个循环中,A这个变量都只是在读取寄存器里面的值。而当进入中断的时候,中断里面会从内存加载A到寄存器......
  • truffle安装问题-无法加载文件
      在powershell下输入以下命令set-executionpolicyremotesigned  问题解决搜索复制......
  • 关于Mybaties数据库链接出现的问题
    最大的bug就是Navicat驼峰studentInfo运行一次过后,惊奇的发现小写也可以运行了。我不李姐!!!......
  • 对异常处理问题的相关思考及总结
    我们已经在课堂上学习了相关的“异常处理”的知识,接下来我们就继续探索异常处理吧!其实,也算得上是对“异常处理”的总结吧,快去看,快去看!知识点一:java.lang.NullPointerExcep......
  • 蛮力法解 01 背包问题
    本文发表在博客园乌漆WhiteMoon(https://www.cnblogs.com/linfangnan/),只要不是在博客园看到这篇文章的都是爬虫的哈。目录蛮力法01背包问题代码编写状态表示约束条件完......
  • 零一背包问题,滚动数组实现
    其实最难理解的内循环,也就是j的循环。j的条件是大于w[i],而w[i]则是当前第i个物品的重量,则j是一在从背包容量,向j-w[i]靠近。j-w[i]就是剩下来的空间,而这一波操作......
  • Mybatis源码环境 碰到的问题
    照着五月仓颉博客敲了一遍测试一直跑不起来出现了以下几个问题1.config.xml&的转义字符要写成&amp;<properties><propertyname="driver"value="com.mysq......
  • Centos 6.6 升级 glibc 问题
    Centos6.6升级glibchttp://ftp.gnu.org/gnu/glibc/glibc-2.14.tar.gzhttp://ftp.gnu.org/gnu/glibc/glibc-2.16.0.tar.gz示例tarxfglibc-2.16.0.tar.gzcdglibc-2.1......
  • 映射xml文件的数据库和实体类属性匹配问题
        实体类里和数据库里有些字段名匹配不上这就会导致即使成功连接数据库,但是由于不匹配的问题无法封装数据,这是在映射的xml文件里提供了一个方法来实现<resultMa......