Tree-String Problem 【CodeForces - 291E】【AC自动机】
程序员文章站
2022-06-04 12:29:42
...
题目链接
题意:给你N个点的树,树上的边的权值是一个自上往下的字符串,然后我们再给出一个字符串,是模式串,我们现在想知道模式串在树上的出现次数,譬如说样例。
我们查找的是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;
}
上一篇: 香甜南瓜饼,软软糯糯香香甜甜就是它