题意:给你N个点的树,树上的边的权值是一个自上往下的字符串,然后我们再给出一个字符串,是模式串,我们现在想知道模式串在树上的出现次数,譬如说样例。
我们查找的是aba,它在1——4这条链上出现了2次,在1——5上出现1次,在2——3上出现2次,在2——6上出现1次。
这道题的做法不是唯一的,譬如说AC自动机也可以解决这个问题。
思路:因为长度确定为模式串的长度,所以又由于总的长度最长只有3e5,所以我们不妨直接拆点来做,我们构建一副新的图,当待查询的长度不足的时候我们继续向下走,当待查询长度满足的时候,我们可以直接判断,当待查询的长度大于1的时候,我们需要用到倍增的LCA来找到上面距离它模式串长度的那个元素,并减去它的哈希值,我们再来判断。
#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;
const ull _hash = 1e9 + 7;
int N, head[maxN], cnt, tot, col[maxN], model_len;
ull del_tim, model;
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++;
}
vector<int> E[maxN];
void build_dfs(int u, int now_root)
{
string ss;
int nex_root;
for(int i=head[u], v, len; ~i; i=edge[i].nex)
{
v = edge[i].to;
ss = edge[i].val; len = (int)ss.size();
nex_root = now_root;
col[++tot] = ss[0];
E[nex_root].push_back(tot);
nex_root = tot;
for(int j=1; j<len; j++)
{
col[++tot] = ss[j];
E[nex_root].push_back(tot);
nex_root = tot;
}
build_dfs(v, nex_root);
}
}
int root[maxN][20] = {0}, ans = 0;
int fid(int u, int x)
{
for(int i=log2(x); i>=0; i--)
{
if((x >> i) & 1) u = root[u][i];
}
return u;
}
void dfs(int u, int have_len, ull hash_val)
{
if(have_len == model_len)
{
if(hash_val == model) ans++;
}
else if(hash_val > model_len)
{
int id = fid(u, model_len);
have_len = model_len;
hash_val -= col[id] * del_tim;
if(hash_val == model) ans++;
}
for(int v : E[u])
{
root[v][0] = u;
for(int i=0; i < 18; i++) root[v][i + 1] = root[root[v][i]][i];
dfs(v, have_len + 1, hash_val * _hash + col[v]);
}
}
inline void init()
{
cnt = tot = 0;
memset(head, -1, sizeof(head));
}
int main()
{
scanf("%d", &N);
init();
string s;
for(int i=2, ff; i<=N; i++)
{
scanf("%d", &ff);
cin >> s;
addEddge(ff, i, s);
}
cin >> s;
model_len = (int)s.size();
del_tim = 1;
for(int i=1; i<=model_len; i++) del_tim = del_tim * _hash;
model = 0;
for(int i=0; i<model_len; i++)
{
model = model * _hash + s[i];
}
build_dfs(1, 0);
dfs(0, 0, 0);
printf("%d\n", ans);
return 0;
}