AC自动机和Fail树

Fail树与阿狸的打字机萌新第一次试着写博客…全是口胡(/□\*),可能以后也不会有时间再写了相关数据结构:AC自动机,树状数组(线段树)Fail指针的基本性质:某只结点的Fail指针,指向它所代表的字符串的最长的后缀的结点。性质:每只结点沿着其Fail指针一直走,最终会走到根节点。这样,将每只结点和其Fail指针指向的结点连边,就形成了一个树,其根与原Trie树相同,称为Fail树。…

大家好,又见面了,我是你们的朋友全栈君。

AC自动机和Fail树

萌新第一次试着写博客…全是口胡(/□\*),可能以后也不会有时间再写了

相关数据结构:AC自动机,树状数组(线段树)

Fail指针的基本性质:某只结点的Fail指针,指向它所代表的字符串的最长的后缀的结点。

性质:每只结点沿着其Fail指针一直走,最终会走到根节点。

这样,将每只结点和其Fail指针指向的结点连边,就形成了一个树,其根与原Trie树相同,称为Fail树。

性质:

1 某个结点 A A A,它子树中的所有节点在Trie图中沿Fail指针一直走,会走到 A A A结点,这说明这些结点所代表的前缀都是 A A A的后缀。

2 该结点沿Fail指针向根走,经过的所有结点所代表的串都是该结点 A A A的后缀。

例子:

对每一个模式串 s i s_i si,将它所有前缀所代表的结点的权值 + 1 +1 +1,再求以 A A A为根的子树的权值和,就是 A A A在所有模式串中出现的次数。

具体地,我们可以递归地求权和,也可以用DFS序,求该结点区间的区间和。(单点更新、区间查询)

还记得吗?AC自动机可以求所有模式串在待匹配串中出现的总次数。

例:[NOI2011]阿狸的打字机
题目描述

打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。经阿狸研究发现,这个打字机是这样工作的:

·输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。

·按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。

·按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。

例如,阿狸输入aPaPBbP,纸上被打印的字符如下:

a aa ab

我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。

阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?

输入输出格式

输入格式:

输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。

第二行包含一个整数m,表示询问个数。

接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为 ( x , y ) (x, y) (x,y)

输出格式:

输出m行,其中第i行包含一个整数,表示第i个询问的答案。

思考:

本题要求任意一个串在给定的串中的出现次数,可能有100000次询问,AC自动机和KMP等等显然都不行。

根据Fail树的性质,一只以结点 A A A为根的子树中的结点,一定含有 A A A串做后缀。那么如果 A A A是某个串的结束结点,那么 A A A串就在这些结点的串中出现过。那么对于另一个串 B B B,它的结点有多少在 A A A子树中出现,那么 A A A就在 B B B中出现了多少次。这就变成了一个子树求和问题。

求子树的权值和可以用上述提到的DFS序结合树状数组来做。但是怎样只求一个特定的串的权值和呢?在遍历Trie树的时候,给当前搜索路径上所有结点的权值 + 1 +1 +1,退出时再 − 1 -1 1,这样就保证只有搜索路径上的结点有权值 1 1 1。每当DFS到一只结束结点时,它所对应的串 B B B的所有节点都在搜索路径上。这样要求 A A A B B B中的出现次数,只要求 A A A子树的权值和就好啦。

预先将查询按照 y y y排序,每DFS到一只结束结点 y y y,就处理该结束结点的所有查询:对每个 ( x , y ) (x,y) (x,y)都进行区间求和的操作,复杂度 O ( l o g n ) O(logn) O(logn)。一共是 O ( ( n + m ) l o g n ) O((n+m)logn) O((n+m)logn)

(祖传的郭老师数算实习课上的AC自动机模板…码风枣糕ヽ(・ω・´メ)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
#define N 100005
#define inf 0x7fffff
#define lb(x) ((x)&-(x))

char s[N];
int nodeCnt = 2, pCnt, q, l;
int dfn[N], Time, Range[N][2], ans[N];

struct Quest{ 
   
    int x, y, index;
    bool operator<(const Quest &op) const { 
    return y < op.y; }
    Quest(){ 
   }
    Quest(int _y):y(_y){ 
   }
}Q[N];

struct Node{ 
   
    Node *child[26], *prev, *fa;
    vector<Node *> fail;
    int poi; //代表打印次序编号
}T[N];

/* 一只树状数组 */
struct TreeA{ 
   
    int C[N];
    void Upd(int x, int v = 1){ 
    while(x<=nodeCnt){ 
   
            C[x]+=v, x+=lb(x);
        }
    }
    int Sum(int x){ 
   
        int sum = 0;
        while(x){ 
   
            sum += C[x];
            x -= lb(x);
        }
        return sum;
    }
    TreeA() { 
    memset(C, 0, sizeof(C)); }
}TA;

void BuildTrie(){ 
   
    Node *now = T + 1;
    for (int i = 0; s[i]; i++){ 
   
        if(s[i]=='P'){ 
   
            now->poi = ++pCnt;
            continue;
        }
        if(s[i]=='B'){ 
   
            now = now->fa;
            continue;
        }
        if(!now->child[s[i]-'a']){ 
   
            now->child[s[i] - 'a'] = T + nodeCnt++;
            now->child[s[i] - 'a']->fa = now;
        }
        now = now->child[s[i] - 'a'];
    }
}

/* 建立一只fail树 */
void BuildFail(){ 
   
    for (int i = 0; i < 26;i++)
        T->child[i] = T + 1;
    (T + 1)->prev = T;
    queue<Node *> q;
    q.push(T + 1);
    while(!q.empty()){ 
   
        Node *now = q.front();
        q.pop();
        for (int i = 0; i < 26;i++)
            if(now->child[i]){ 
   
                Node *prev = now->prev;
                while(!prev->child[i])
                    prev = prev -> prev;
                now->child[i]->prev = prev->child[i];
                prev->child[i]->fail.push_back(now->child[i]);
                q.push(now->child[i]);
            }
    }
}

/* 遍历Fail树,找到它的DFS序 */
void DFN(Node* r){ 
   
    dfn[r - T] = ++Time;
    for (int i = 0; i < r->fail.size(); i++)
        DFN(r->fail[i]);
    if(r->poi)
        Range[r->poi][1] = Time,Range[r->poi][0]=dfn[r-T];
}

/* 遍历Trie树,不断处理查询 */
void DFS(Node* r){ 
   
    TA.Upd(dfn[r - T]);   /* 搜索路径上结点权值+1 */
    if(r->poi){ 
   
        int now = lower_bound(Q, Q + q, Quest(r->poi)) - Q;
        for (; Q[now].y == r->poi;now++){ 
   
            int x = Q[now].x;
            ans[Q[now].index] = TA.Sum(Range[x][1]) - TA.Sum(Range[x][0] - 1);
        }
    }
    for (int i = 0; i < 26;i++)
        if(r->child[i])
            DFS(r->child[i]);
    TA.Upd(dfn[r - T], -1); /* 不在搜索路径上了 权值为0 */
}

int main(){ 
   
    scanf("%s", s);
    BuildTrie();
    BuildFail();
    DFN(T+1);
    cin >> q;
    for (int i = 0; i < q;i++){ 
   
        scanf("%d%d", &Q[i].x, &Q[i].y);
        Q[i].index = i;
    }
    sort(Q, Q + q);
    DFS(T+1);
    for (int i = 0; i < q;i++)
        printf("%d\n", ans[i]);
    return 0;
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/126257.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • PHP生成随机数(昵称随机生成器)

    <?php/***@paramint$type1生成昵称,2生成姓名*//汉语-给用户自动生成昵称*/functionnickname($type=1){/***随机昵称形容词*/$nicheng_tou=[‘迷你的’,’鲜艳的’,’飞快的’,’真实的’,’清新的’,’幸福的’,’可耐的’,’快乐的’,’冷静的’,’醉熏的’,’潇洒的’,’糊涂的’,’积极的’,’冷酷的’,’深情的’,’粗暴的’,’温

  • BOM的介绍_BOM定义

    BOM的介绍_BOM定义BOM的概念BOM(BrowserObjectModel)是指浏览器对象模型。浏览器对象模型提供了独立于内容的、可以与浏览器窗口进行互动的对象结构。BOM由多个对象组成,其中代表浏览器窗口

  • 文件共享服务 FTP,NFS 和 Samba

    文件共享服务 FTP,NFS 和 Samba

  • AOI之十字链表法

    AOI之十字链表法1.简介AOI主要有九宫格、灯塔和十字链表的算法实现。本文阐述十字链表的实现2. 基本原理若是二维地图,将地图内的对象按照坐标值,从小到大分在x轴和y轴两个链表上。如果是三维地图,则还需要维护多一个z轴的链表3.基本接口 Add:对象进入场景Move:对象在场景内移动Leave:对象离开场景4.代码如下scene.h#ifndef__CScene_H__#define__CScene_…

  • 【深度学习】回归问题损失函数——均方误差(MSE)

    【深度学习】回归问题损失函数——均方误差(MSE)本文主要介绍回归问题的损失函数——均方误差,以及TensorFlow的实现。

  • PLSQL基本操作手册

    PLSQL基本操作手册公众号:池哥搬砖QQ1群:745460286个人WX公号:目录第1章用PLSQL连接Oracle数据库§1.2登录信息保存功能设置:§1.3进入PLSQL后切换数据库连接:第2章PLSQL中编写SQL语句并执行第3章PLSQL中查看数据库表结构§3.1查看表结构:§3.2表结构窗口和SQL编写窗口切换:第4章…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号