[Codeforces291E]Tree-String Problem（hash+倍增）

题目描述

传送门

题解

可以将所有的字符串拆成一个一个的点，每一个点都只有一个字符 首先算出模式串的hash值 然后对于每一个点计算出从根到这个点形成的串的hash值 枚举每一个点，倍增求出与它的距离为模式串的长度的父亲，然后计算这一段的hash值 统计答案即可

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define UL unsigned long long #define N 300005 #define sz 19 const UL S=2000001001; int n,cnt,len,ans; char s[N]; int tot,point[N],nxt[N],v[N]; int c[N],f[N][sz+3]; UL mi,model,hash[N]; void add(int x,int y) { ++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y; } void build(int x,int fa) { hash[x]=hash[fa]*S+(UL)c[x]; for (int i=1;i<sz;++i) f[x][i]=f[f[x][i-1]][i-1]; for (int i=point[x];i;i=nxt[i]) { f[v[i]][0]=x; build(v[i],x); } } int find(int x,int k) { for (int i=0;i<sz;++i) if ((k>>i)&1) x=f[x][i]; return x; } void dfs(int x) { int fa=find(x,len); if (fa) { UL HASH=hash[x]-hash[fa]*mi; if (HASH==model) ++ans; } for (int i=point[x];i;i=nxt[i]) dfs(v[i]); } int main() { scanf("%d",&n);c[1]='#';cnt=n; for (int i=2;i<=n;++i) { int fa;scanf("%d",&fa); scanf("%s",s);len=strlen(s); if (len>1) { c[++cnt]=s[0];add(fa,cnt); for (int j=1;j<len-1;++j) { ++cnt; add(cnt-1,cnt);c[cnt]=s[j]; } add(cnt,i),c[i]=s[len-1]; } else c[i]=s[0],add(fa,i); } scanf("%s",s);len=strlen(s); mi=1LL;for (int i=len-1;i>=0;--i) model+=(UL)s[i]*mi,mi*=S; n=cnt; build(1,0); dfs(1); printf("%d\n",ans); }