icontofig | 发布于 2020-02-19 22:10:38 | 阅读量 535 | 字符串 可持久化线段树 可持久化数据结构 Trie

Input

5 5
a
ab
abab
ababab
b
1 5 1
3 5 1
1 5 2
1 5 3
1 4 5

Output

7
5
6
3
6

题目大意

给出n个字符串,q次询问,每次询问l,r,k,求问

字符串l——r中,包含字符串k(字符串k作为子串)的字符串个数是多少。

题解

多模式串匹配肯定是AC自动机

但是这个问题是多个串中有多少能匹配到当前询问的这一个字串的问题,而不是经典的某个串能匹配多少个已经给出的串的问题。

AC自动机的Trie树中,某个节点的所有祖先节点表示一个或几个字符串在当前这个位置之前的字符串前缀。所以对于某个结束节点来说,他的所有祖先节点加上他本身构成了一个字符串。

而对于AC自动机建立的fail树来说,一个节点的fail指针指向的节点以及其trie树上的祖先一定构成了当前节点到trie树的根节点所表示的字符串的一个后缀。如果其fail指针指向的是一个结束节点,那么这个串就一定能匹配它的fail指针指向节点在trie树所代表的一个字符串,也就是完成了一个子串匹配。

于是我们可以借助这一点性质,来求解能匹配ac自动机中第k个字符串的字符串个数,方法是:

沿着当指向当前节点的fail路径的反方向走,每走到一个节点ans+1,最终无路可走时,得到的就是答案。(包括这个字符串本身)。、

但是这个题还有在区间[l,r]的字符串的限制。

考虑到普通的线段树没法做到这种询问,所以我们应该想到这个题可以用可持久化线段树来做。

可持久化线段树最大的特点就是每棵线段树的根节点都代表着一次更新的时间戳,我们可以利用这个时间戳去求区间的一个值。

但是这是一个AC自动机上的问题,准确的来说是fail树上的问题,如何建线段树?

对于树上问题,可以先想树链剖分,其本质就是求DFS序,所以我们也可以对fail树构建DFS序,然后在此基础依次添加每个串,构建可持久化线段树。

根据上面的fail树上的性质来说,通过fail路径的反方向路径构成的fail树,某个节点的子节点都是原先的fail指针指向当前节点的节点,也是我们要统计路径时走向的节点。

某个节点的子树,代表了能匹配到以此节点到trie树根节点构成的字符串的后缀的所有字符串所在的fail树的位置。

我们根据fail路径来构建DFS序,在此基础上建立可持久化线段树。在建立可持久化线段树的过程中,每添加一个字符串,都要对这个字符串在AC自动机Trie树上对应的所有节点按字符串反向序列建一个新的线段树(正向的话在AC自动机里面走路径太烦了),因此应该怎样设置时间戳需要稍微注意一下,应该是当前字符串加完以后的时间戳。

后面的问题就是在可持久化线段树上询问了,很基础的部分了,看代码就行了。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5+5;
struct seg{
    int l,r,val,lc,rc;
}tr[maxn*25];
int tot = 0;
vector<int>g[maxn];
int pos[maxn];
struct Trie{
    int nex[maxn][26], fail[maxn], fa[maxn];
    int root, p;
    inline int newnode() {
        for (int i = 0; i < 26; ++i) {
            nex[p][i] = -1;
        }
        p++;
        return p - 1;
    }
    inline void init() {
    	p = 0;
    	root = newnode();
    }
    inline void insert(char *buf,int id) {
        int now = root;
        for (int i = 0; buf[i]; ++i) {
            if (nex[now][buf[i]-'a'] == -1) 
                nex[now][buf[i]-'a'] = newnode();
            fa[nex[now][buf[i]-'a']] = now;
            now = nex[now][buf[i]-'a'];
        }
        pos[id] = now;
        return;
    } 
    inline void build() {
        queue<int> que;
        fail[root] = root;
        for (int i = 0; i < 26; ++i) {
            if (nex[root][i] == -1)
                nex[root][i] = root;
            else {
                fail[nex[root][i]] = root;
                g[root].push_back(nex[root][i]);
                que.push(nex[root][i]);
            }
        }
        while (!que.empty()) {
            int now = que.front();
            que.pop();
            for (int i = 0; i < 26; ++i) {
                if (nex[now][i] == -1) 
                    nex[now][i] = nex[fail[now]][i];
                else {
                    fail[nex[now][i]] = nex[fail[now]][i];
                    g[fail[nex[now][i]]].push_back(nex[now][i]);
                    que.push(nex[now][i]);
                }
            }
        }
    }
}AC;
void push_up(int now){
    tr[now].val = tr[tr[now].lc].val + tr[tr[now].rc].val;
    return;
}
int dfs_clock,dl[maxn],dr[maxn];
int build(int l,int r){
    int now = ++tot;
    tr[now].l = l;
    tr[now].r = r;
    tr[now].val = 0;
    if(l == r)
        return now;
    int mid = (l + r) >> 1;
    tr[now].lc = build(l,mid);
    tr[now].rc = build(mid + 1,r);
    push_up(now);
    return now;
}
int update(int pre,int pos,int v){
    int now = ++tot;
    tr[now] = tr[pre];
    if(tr[now].l == tr[now].r){
        tr[now].val = tr[pre].val + v;
        return now;
    }
    int mid = (tr[now].l + tr[now].r) >> 1;
    if(pos <= mid)
        tr[now].lc = update(tr[pre].lc,pos,v);
    else tr[now].rc = update(tr[pre].rc,pos,v);
    push_up(now);
    return now;
}
int query(int ll,int rr,int l,int r){
    if(tr[rr].l >= l && tr[rr].r <= r){
        return tr[rr].val - tr[ll].val;
    }
    int mid = (tr[rr].l + tr[rr].r) >> 1;
    int ans = 0;
    if(l <= mid)ans += query(tr[ll].lc,tr[rr].lc,l,r);
    if(r > mid)ans += query(tr[ll].rc,tr[rr].rc,l,r);
    return ans;
}
void dfs(int now){
    dl[now] = dfs_clock++;
    for(int i = 0;i < g[now].size();++i)
        dfs(g[now][i]);
    dr[now] = dfs_clock - 1;
    return;
}
int root[maxn],st[maxn];
int n,q;
char s[maxn];
int l,r,k,ql,qr;
int cur = 0;
int main(){
    scanf("%d%d",&n,&q);
    AC.init();
    for(int i = 1;i <= n;++i){
        scanf("%s",s);
        AC.insert(s,i);
    }
    AC.build();
    dfs(0);
    root[0] = build(1,AC.p - 1);
    for(int i = 1;i <= n;++i){
        int now = pos[i];
        while(now){
            cur++;
            root[cur] = update(root[cur-1],dl[now],1);
            now = AC.fa[now];
        }
        st[i] = root[cur];
    }
    while(q--){
        scanf("%d%d%d",&l,&r,&k);
        ql = dl[pos[k]];qr = dr[pos[k]];
        printf("%d\n",query(st[l-1],st[r],ql,qr));
    }
    return 0;
}



内容更新于: 2020-02-19 22:10:42
链接地址: http://blog.leanote.com/post/icontofig/13f7816f015f

上一篇: CodeForces 1303F. Number of Components 并查集

下一篇: CodeForces 710F. String Set Queries 模拟二进制堆启发式合并的AC自动机合并

535 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航