欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Tree-String Problem 【CodeForces - 291E】【AC自动机】

程序员文章站 2022-06-04 12:29:42
...

题目链接


  题意:给你N个点的树,树上的边的权值是一个自上往下的字符串,然后我们再给出一个字符串,是模式串,我们现在想知道模式串在树上的出现次数,譬如说样例。

Tree-String Problem 【CodeForces - 291E】【AC自动机】

  我们查找的是aba,它在1——4这条链上出现了2次,在1——5上出现1次,在2——3上出现2次,在2——6上出现1次。

  思路:我们可以直接建模式串的字典树,然后先赋值上价值1,然后后面我们只需要在AC自动机上知道价值1出现的次数就可以了,直接fail跳转即可。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <limits>
#include <vector>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <bitset>
#include <unordered_map>
#include <unordered_set>
#define lowbit(x) ( x&(-x) )
#define pi 3.141592653589793
#define e 2.718281828459045
#define INF 0x3f3f3f3f
#define HalF (l + r)>>1
#define lsn rt<<1
#define rsn rt<<1|1
#define Lson lsn, l, mid
#define Rson rsn, mid+1, r
#define QL Lson, ql, qr
#define QR Rson, ql, qr
#define myself rt, l, r
using namespace std;
typedef unsigned long long ull;
typedef unsigned int uit;
typedef long long ll;
const int maxN = 3e5 + 7;
int N, head[maxN], cnt, tot;
struct Eddge
{
    int nex, to; string val;
    Eddge(int a=-1, int b=0, string c=""):nex(a), to(b), val(c) {}
}edge[maxN << 1];
inline void addEddge(int u, int v, string w)
{
    edge[cnt] = Eddge(head[u], v, w);
    head[u] = cnt++;
}
struct node
{
    int nex[26], val, fail, tim;
    inline void clear() { memset(nex, 0, sizeof(nex)); val = fail = tim = 0; }
}a[maxN];
void Insert_Trie_Model(string model)
{
    int len = (int)model.size(), root = 0;
    for(int i=0, ch; i<len; i++)
    {
        ch = model[i] - 'a';
        if(!a[root].nex[ch])
        {
            ++tot;
            a[tot].clear();
            a[root].nex[ch] = tot;
        }
        root = a[root].nex[ch];
    }
    a[root].val = 1;
}
void dfs(int u, int fa, int now_root)
{
    string ss;
    int nex_root = now_root;
    for(int i=head[u], v, len, ch; ~i; i=edge[i].nex)
    {
        v = edge[i].to;
        if(v == fa) continue;
        ss = edge[i].val;
        nex_root = now_root;
        len = (int)ss.size();
        for(int j=0; j<len; j++)
        {
            ch = ss[j] - 'a';
            if(!a[nex_root].nex[ch])
            {
                ++tot;
                a[tot].clear();
                a[nex_root].nex[ch] = tot;
            }
            nex_root = a[nex_root].nex[ch];
            a[nex_root].tim ++;
        }
        dfs(v, u, nex_root);
    }
}
int ans = 0;
void build_fail()
{
    queue<int> Q; Q.push(0);
    int tmp, p, son;
    while(!Q.empty())
    {
        tmp = Q.front(); Q.pop();
        for(int i=0; i<26; i++)
        {
            son = a[tmp].nex[i];
            if(son)
            {
                if(!tmp)
                {
                    a[son].fail = 0;
                }
                else
                {
                    p = a[tmp].fail;
                    while(p && !a[p].nex[i]) p = a[p].fail;
                    a[son].fail = a[p].nex[i];
                }
                if(a[a[son].fail].val)
                {
                    a[son].val += a[a[son].fail].val;
                    ans += a[a[son].fail].val * a[son].tim;
                }
                Q.push(son);
            }
            else a[tmp].nex[i] = a[a[tmp].fail].nex[i];
        }
    }
}
inline void init()
{
    cnt = tot = 0;
    a[0].clear();
    memset(head, -1, sizeof(head));
}
string s;
int main()
{
    scanf("%d", &N);
    init();
    for(int i=2, ff; i<=N; i++)
    {
        scanf("%d", &ff);
        cin >> s;
        addEddge(ff, i, s);
    }
    cin >> s;
    Insert_Trie_Model(s);
    dfs(1, 0, 0);
    build_fail();
    ans += a[s.size()].val * a[s.size()].tim;
    printf("%d\n", ans);
    return 0;
}

 

相关标签: AC自动机