本文共 1030 字，大约阅读时间需要 3 分钟。
就是SAM嘛。
答案累加就是dep[parent[now]]-dep[now]
有个比较坑的就是要用map。。
#include #include #include #include #include #include #include using namespace std;typedef long long LL;int a[210000];map ch[410000];int root,last,cnt;LL ans;int parent[410000],dep[410000];void add(int k){ int x=a[k]; int now=++cnt,p=last; dep[now]=k; while(p!=0&&ch[p][x]==0) ch[p][x]=now,p=parent[p]; if(p==0)parent[now]=root; else { int pre=ch[p][x]; if(dep[pre]==dep[p]+1)parent[now]=pre; else { int npre=++cnt; ch[npre]=ch[pre]; parent[npre]=parent[pre]; dep[npre]=dep[p]+1; parent[now]=parent[pre]=npre; while(p!=0&&ch[p][x]==pre) ch[p][x]=npre,p=parent[p]; } } last=now; if(parent[now]==0)ans+=(LL(dep[now])); else ans+=(LL(dep[now]-dep[parent[now]]));}int main(){ int n; scanf("%d",&n); root=last=cnt=1;ans=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]),add(i); printf("%lld\n",ans); } return 0;}
转载于:https://www.cnblogs.com/AKCqhzdy/p/8693601.html