首页 > 代码库 > 51Nod 1600 Simple KMP SAM+LCT/树链剖分
51Nod 1600 Simple KMP SAM+LCT/树链剖分
1600 Simple KMP
对于一个字符串|S|,我们定义fail[i],表示最大的x使得S[1..x]=S[i-x+1..i],满足(x<i)
显然对于一个字符串,如果我们将每个0<=i<=|S|看成一个结点,除了i=0以外i向fail[i]连边,这是一颗树的形状,根是0
我们定义这棵树是G(S),设f(S)是G(S)中除了0号点以外所有点的深度之和,其中0号点的深度为-1
定义key(S)等于S的所有非空子串S‘的f(S‘)之和
给定一个字符串S,现在你要实现以下几种操作:
1.在S最后面加一个字符
2.询问key(S)
善良的出题人不希望你的答案比long long大,所以你需要将答案对1e9+7取模
显然对于一个字符串,如果我们将每个0<=i<=|S|看成一个结点,除了i=0以外i向fail[i]连边,这是一颗树的形状,根是0
我们定义这棵树是G(S),设f(S)是G(S)中除了0号点以外所有点的深度之和,其中0号点的深度为-1
定义key(S)等于S的所有非空子串S‘的f(S‘)之和
给定一个字符串S,现在你要实现以下几种操作:
1.在S最后面加一个字符
2.询问key(S)
善良的出题人不希望你的答案比long long大,所以你需要将答案对1e9+7取模
Input
第一行一个正整数QQ<=10^5第二行一个长度为Q的字符串S
Output
输出Q行,第i行表示前i个字符组成的字符串的答案
Input示例
5abaab
Output示例
00149
SkyDec (题目提供者)
链接:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1600
一开始想错了,于是去写LCT+SAM。然后发现竟然撞上正解了......
想法:首先明白只需统计每次加入的点连到每个后缀的Next树的深度,真正的答案可以求前缀和得到。
然后发现Next树的一个节点的深度,其实就是以该点为结尾的后缀能匹配多少前缀(长度长的可以包含短的,连最长的就构成Next树了)。
于是问题变成了以该点为结尾的后缀在原串中出现多少次,这个可以用SAM的parent树的right以及step求出来。
可以使用LCT+SAM,或者离线后树剖维护一下。
突然发现我的LCT比我的树剖快.....
Code
#include < cstdio >#define gec getchar #define FILE(F) freopen(F".in","r",stdin),freopen(F".out","w",stdout)#define DEBUG fprintf(stderr,"Passing [%s] in Line (%d)\n",__FUNCTION__,__LINE__)typedef long long ll;templateinline void read(T&x){ x=0;bool f=0;char c=gec(); for(;c<‘0‘||c>‘9‘;c=gec())f=(c==‘-‘); for(;c>=‘0‘&&c<=‘9‘;c=gec())x=x*10+c-‘0‘; x=f?-x:x;}const int MAXN(100010),MP(1e9+7);int n;char str[MAXN];void plus(int &x,int y){x+=y;x-=x>=MP?MP:0;}namespace Force_LCT{ struct LCT { int nx[2],fa; int step,right; int Sum_step,Tag,Sum;//Son need +Tag? }tr[MAXN<<1]; void swap(int &x,int &y){int t(x);x=y;y=t;} int which(int x){if(tr[tr[x].fa].nx[0]==x)return 0;if(tr[tr[x].fa].nx[1]==x)return 1;return -1;} void push(int x) { if(!tr[x].Tag)return; plus(tr[tr[x].nx[0]].Tag,tr[x].Tag); plus(tr[tr[x].nx[0]].right,tr[x].Tag); plus(tr[tr[x].nx[0]].Sum,(ll)tr[x].Tag*tr[tr[x].nx[0]].Sum_step%MP); plus(tr[tr[x].nx[1]].Tag,tr[x].Tag); plus(tr[tr[x].nx[1]].right,tr[x].Tag); plus(tr[tr[x].nx[1]].Sum,(ll)tr[x].Tag*tr[tr[x].nx[1]].Sum_step%MP); tr[x].Tag=0; } void update(int x) { tr[x].Sum=((ll)tr[x].step*tr[x].right)%MP; tr[x].Sum_step=tr[x].step; if(tr[x].nx[0])plus(tr[x].Sum,tr[tr[x].nx[0]].Sum),plus(tr[x].Sum_step,tr[tr[x].nx[0]].Sum_step); if(tr[x].nx[1])plus(tr[x].Sum,tr[tr[x].nx[1]].Sum),plus(tr[x].Sum_step,tr[tr[x].nx[1]].Sum_step); } void rotate(int x) { int fa=tr[x].fa,fafa=tr[fa].fa,fd=which(fa),xd=which(x); tr[tr[x].nx[xd^1]].fa=fa; tr[fa].nx[xd]=tr[x].nx[xd^1]; tr[x].nx[xd^1]=fa;tr[fa].fa=x; tr[x].fa=fafa;if(fd!=-1)tr[fafa].nx[fd]=x; update(fa); } int st[MAXN<<1],tp; void splay(int x) { st[tp=1]=x; for(int t=x;which(t)!=-1;t=tr[t].fa)st[++tp]=tr[t].fa; while(tp)push(st[tp--]); while(which(x)!=-1) { int fa=tr[x].fa; if(which(fa)!=-1) rotate( which(x)^which(fa)? fa : x ); rotate(x); } update(x); } void access(int x) { for(int t=0;x;t=x,x=tr[x].fa) { splay(x); tr[x].nx[1]=t; update(x); } } void cut(int x,int y)//x‘s fa is y { access(x); splay(y); tr[y].nx[1]=0; update(y); tr[x].fa=0; } void link(int x,int y)//x‘s fa is y { splay(y); tr[x].fa=y; } }namespace Force_SAM{ using namespace Force_LCT; struct SAM { int nx[26],pre,step,right; }sam[MAXN<<1];int top=1,now=1,root=1,last,lastson; void New(int x) { tr[x].right=sam[x].right; tr[x].step=sam[x].step-sam[sam[x].pre].step; update(x); } void entend(int x,int &S,int num) { last=now; now=++top; sam[now].step=sam[last].step+1; sam[now].right=1; for(;!sam[last].nx[x]&&last;last=sam[last].pre) sam[last].nx[x]=now; if(!last)sam[now].pre=root; else { lastson=sam[last].nx[x]; if(sam[lastson].step==sam[last].step+1)sam[now].pre=lastson; else { sam[++top]=sam[lastson]; sam[top].step=sam[last].step+1; splay(lastson); sam[top].right=sam[lastson].right=tr[lastson].right; New(top); link(top,sam[top].pre); cut(lastson,sam[lastson].pre); sam[now].pre=sam[lastson].pre=top; New(lastson); link(lastson,sam[lastson].pre); for(;sam[last].nx[x]==lastson&&last;last=sam[last].pre) sam[last].nx[x]=top; } } New(now); link(now,sam[now].pre); access(now); splay(now); S=tr[tr[now].nx[0]].Sum; plus(tr[tr[now].nx[0]].Tag,1); plus(tr[tr[now].nx[0]].right,1); plus(tr[tr[now].nx[0]].Sum,tr[tr[now].nx[0]].Sum_step); } int F[MAXN]; void Total() { New(1); for(int i=1;i<=n;i++) { entend(str[i]-‘a‘,F[i],i); plus(F[i],F[i-1]); } for(int i=1;i<=n;i++)plus(F[i],F[i-1]); for(int i=1;i<=n;i++)printf("%d\n",F[i]); } }int main(){ read(n);scanf("%s",str+1); Force_SAM::Total(); return 0;}
51Nod 1600 Simple KMP SAM+LCT/树链剖分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。