后缀三兄弟&回文双子星

orz hhw posted @ 2015年7月20日 17:03 in 算法学习 with tags 字符串 模板 后缀数组 后缀自动机 算法学习 bzoj Manacher 回文自动机 , 5489 阅读

字符串这一块一直都不太懂,处理前缀的还好,Tire、AC自动机什么的比较好理解,代码也好记。但后缀三兄弟我就完全不懂啦,而且最近总是喜欢考后缀三兄弟,省选考后缀自动机直接写个暴力Tire滚粗了,NOI考后缀数组直接拉板但是不知道怎么去处理、、虽然后缀数组、后缀自动机看了好几遍,但还是完全不会写,今天把他们好好学了下。

一、后缀数组

先给后缀数组模板加了下注释,差不多懂了,到时候多看看就好了,由于BZOJ上找不到题,也没法用,到时候把NOI这道题做掉吧

#include<cstdio>
#include<cstring>
#define N 510000
int cmp(int *r,int a,int b,int l){return (r[a]==r[b])&(r[a+l]==r[b+l]);}//用于比较第一关键字与第二关键字,
//比较特殊的地方是,预处理的时候,r[n]=0(小于前面出现过的字符)
int min(int x,int y){if(x<y)return x;return y;}
int ws[N],wv[N],sa[N],rank[N],rank2[N],height[N],er[21],log2[N],f[N][21],n,t;
char str[N];
void DA(char *r,int *sa,int n,int m){//此处N比输入的N要多1,为人工添加的一个字符,用于避免CMP时越界
    int i,j,p,*x=rank,*y=rank2,*t;//x存rank,y是第二关键字 
    for(i=0;i<m;i++)ws[i]=0;
    for(i=0;i<n;i++)ws[x[i]=r[i]]++;
    for(i=1;i<m;i++)ws[i]+=ws[i-1];
    for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;//预处理长度为1
    for(j=1,p=1;p<n;j*=2,m=p){//通过已经求出的长度J的SA,来求2*J的SA
        for(p=0,i=n-j;i<n;i++)y[p++]=i;//特殊处理没有第二关键字的
        for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;//利用长度J的,按第二关键字排序
        for(i=0;i<n;i++)wv[i]=x[y[i]];
        for(i=0;i<m;i++)ws[i]=0;
        for(i=0;i<n;i++)ws[wv[i]]++;
        for(i=1;i<m;i++)ws[i]+=ws[i-1];
        for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];//基数排序部分
        for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
            x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;//更新名次数组x[],注意判定相同的
    }
}
void calheight(char *r,int *sa,int n){ // 此处N为实际长度
    int i,j,k=0;//height[]的合法范围为 1-N, 其中0是结尾加入的字符
    for(i=0;i<n;height[rank[i++]]=k)//定义height[i]=height[rank[i]]
    for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);//根据height[i]>=height[i-1]-1来优化计算height过程
}
void RMQ(){//对height数组 
     int i,j;er[0]=1;  
     for(i=1;i<20;i++)er[i]=er[i-1]*2;  
     log2[0]=-1;  
     for(i=1;i<=n;i++)log2[i]=(i&(i-1))?log2[i-1]:log2[i-1]+1;  
     for(i=1;i<=n;i++)f[i][0]=height[i];  
     for(j=1;j<20;j++)  
         for(i=1;i+er[j]-1<=n;i++)  
             f[i][j]=min(f[i][j-1],f[i+er[j-1]][j-1]);  
}
int lcp(int a,int b){//求公共前缀lcp 
     int x=rank[a],y=rank[b];
     if(x>y)t=x,x=y,y=t;  
     x++;int k=log2[y-x+1];  
     return min(f[x][k],f[y-er[k]+1][k]);  
} 
int main(){
	scanf("%s",str);
    n=strlen(str);str[n]=0;
    DA(str,sa,n+1,128);//注意区分此处为n+1,因为添加了一个结尾字符用于区别比较
	calheight(str,sa,n);
	RMQ();
}

BZOJ3238:和NOI Day2 70分算法相同,考试时候拉模板结果模板错了导致只拿了40分、、

做这道题时改了好久,想想单调栈应该没问题,原来是后缀数组模板炸了、、改一下就A了。。

#include<cstdio>
#include<cstring>
#define N 555555
int n,head,i,ws[N],wv[N],sa[N],rank[N],rank2[N],height[N],q[N],lc[N],rc[N];
long long ans;char s[N];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&r[a+l]==r[b+l];}
void DA(char *r,int *sa,int n,int m){
	int i,j,p,*x=rank,*y=rank2,*t;
	for(i=0;i<m;i++)ws[i]=0;
	for(i=0;i<n;i++)ws[x[i]=r[i]]++;
	for(i=0;i<m;i++)ws[i]+=ws[i-1];
	for(i=n-1;i>=0;i--)sa[--ws[x[i]]]=i;
	for(j=1;p<n;j*=2,m=p){
		for(p=0,i=n-j;i<n;i++)y[p++]=i;
		for(i=0;i<n;i++)if(sa[i]>=j)y[p++]=sa[i]-j;
		for(i=0;i<n;i++)wv[i]=x[y[i]];
		for(i=0;i<m;i++)ws[i]=0;
		for(i=0;i<n;i++)ws[wv[i]]++;
		for(i=0;i<m;i++)ws[i]+=ws[i-1];
		for(i=n-1;i>=0;i--)sa[--ws[wv[i]]]=y[i];
		for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++)
			x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++;
	}
}
void calheight(char *r,int *sa,int n){
    int i,j,k=0;
    for(i=1;i<=n;i++)rank[sa[i]]=i;
    for(i=0;i<n;height[rank[i++]]=k)
        for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++);
}
int main(){
	scanf("%s",s);n=strlen(s);
	DA(s,sa,n+1,128);
	calheight(s,sa,n);
	ans=(long long)(n-1)*(long long)n*((long long)n+1)/2;  
	height[0]=-1e9;q[1]=1;lc[1]=1;head=1;
	for(i=2;i<=n;i++){
		while(head&&height[i]<=height[q[head]])head--;
		lc[i]=i-q[head];
		q[++head]=i;
	}
	height[n+1]=-1e9;q[0]=n+1;q[1]=n;rc[n]=1;head=1;
	for(i=n-1;i;i--){
		while(head&&height[i]<height[q[head]])head--;
		rc[i]=q[head]-i;
		q[++head]=i;
	}
	for(i=1;i<=n;i++)ans-=(long long)(2*height[i])*(long long)(lc[i])*(long long)(rc[i]);
	printf("%lld",ans);
}

二、后缀自动机&后缀树

后缀自动机一开始还是看晕了,于是先看了下后缀树,感觉能理解,不过不知道代码怎么写

然后结合文章和代码看后缀自动机,差不多搞懂了,感觉后缀自动机的代码还是挺短挺好理解的,争取多用用

SPOJ这道题蛮神的,虽然不理解,但先作为模板写一遍吧

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 555555
using namespace std;
char s[N];int S,cnt,last,n,i,p,a[N],b[N],f[N],t[N],fa[N],step[N],r[N],son[N][26];
void add(int x){
	int c=a[x],p=last,np=++cnt;last=np;//最新添加节点的位置 
	step[np]=x;
	for(;p&&!son[p][c];p=fa[p])son[p][c]=np;//不断走失败节点,如果走到的节点没有x儿子将x插入,否则退出 
	if(!p)fa[np]=S;else{//如果走到根节点,将np的失败指针指到根 
		int q=son[p][c];
		if(step[p]+1==step[q])fa[np]=q;else{//记录所走步数,如果符合条件将np失败指针指到last 
			int nq=++cnt;step[nq]=step[p]+1;//新建一个节点nq代替q节点 
			memcpy(son[nq],son[q],sizeof son[q]);//所以将q节点的值复制给nq 
			fa[nq]=fa[q];fa[np]=fa[q]=nq;//重新构造失败指针 
			for(;son[p][c]==q;p=fa[p])son[p][c]=nq;//不断走失败节点将儿子nq插入直到存在 
		}
	}
}
int main(){
	scanf("%s",s+1);
	last=S=++cnt;
	int n=strlen(s+1);
	for(i=1;i<=n;i++)a[i]=s[i]-'a',add(i);
	for(i=1,p=S;i<=n;i++)r[p=son[p][a[i]]]++;
	for(i=1;i<=cnt;i++)b[step[i]]++;
	for(i=1;i<=n;i++)b[i]+=b[i-1];
	for(i=1;i<=cnt;i++)t[b[step[i]]--]=i;
	for(i=cnt;i;i--)r[fa[t[i]]]+=r[t[i]];
	for(i=1;i<=cnt;i++)f[step[i]]=max(f[step[i]],r[i]);
	for(i=n;i;i--)f[i]=max(f[i+1],f[i]);
	for(i=1;i<=n;i++)printf("%d\n",f[i]); 
}

SPOJ1812:多串LCM

将一个串建SAM,剩下的串去匹配,对于每个串保存最大值,多串保存最小值,好神啊

#include<cstdio>
#include<cstring>
#include<iostream>
#define N 222222
using namespace std;
int last,S,i,n,cnt,tmp,p,ans,c,np,q,nq,mn[N],fa[N],step[N],v[N],w[N],cl[N],son[N][26];
char s[N];
void add(int x){
	c=s[x]-'a',p=last,last=np=++cnt;step[np]=step[p]+1;
	for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
	if(!p)fa[np]=S;else{
		q=son[p][c];
		if(step[p]+1==step[q])fa[np]=q;else{
			nq=++cnt;step[nq]=step[p]+1;
			memcpy(son[nq],son[q],sizeof son[q]);
			fa[nq]=fa[q];fa[np]=fa[q]=nq;
			for(;son[p][c]==q;p=fa[p])son[p][c]=nq;
		}
	}
}
int main(){
	scanf("%s",s);n=strlen(s);
	last=S=++cnt;
	for(i=0;i<n;i++)add(i);
	for(i=1;i<=cnt;i++)mn[i]=step[i];
	for(i=1;i<=cnt;i++)v[step[i]]++;
	for(i=1;i<=n;i++)v[i]+=v[i-1];
	for(i=1;i<=cnt;i++)w[v[step[i]]--]=i;
	while(scanf("%s",s)!=EOF){
		n=strlen(s);memset(cl,0,sizeof(cl));tmp=0;
		for(p=1,i=0;i<n;i++){
			c=s[i]-'a';
			if(son[p][c])p=son[p][c],tmp++;else{
				while(p&&!son[p][c])p=fa[p];
				if(!p)p=1,tmp=0;else tmp=step[p]+1,p=son[p][c];
			}
			cl[p]=max(cl[p],tmp);
		}
		for(i=cnt;i;i--){
			int t=w[i];
			mn[t]=min(mn[t],cl[t]);
			if(cl[t]&&fa[t])cl[fa[t]]=step[fa[t]];
		}
	}
	for(i=1;i<=cnt;i++)ans=max(ans,mn[i]);
	printf("%d",ans);
}

BZOJ2555:现在暴力似乎过不了

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 1666666
using namespace std;
int last,S,mask,i,cnt,c,p,np,q,nq,x,m,n,ans,son[N][26],fa[N],size[N],step[N];
char ch[99],s[N];
void DecodeWithMask(int mask){
	for(int i=0;i<n;++i) {
		mask=(mask*131+i)%n;
		swap(s[i],s[mask]);
	}
}
void add(int x){
	c=s[x]-'A';p=last;last=np=++cnt;step[np]=step[p]+1;
	for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
	if(!p)fa[p]=S;else{
		q=son[p][c];
		if(step[p]+1==step[q])fa[np]=q;else{
			nq=++cnt;step[nq]=step[q];
			memcpy(son[nq],son[q],sizeof son[q]);
			fa[nq]=fa[q];fa[q]=fa[np]=nq;size[nq]=size[q];
			for(;son[p][c]==q;p=fa[p])son[p][c]=nq;
		}
	}
	for(last=np;np!=S;np=fa[np])size[np]++;
}
int query(){
	int i,x=S,c;
	for(i=0;s[i];i++)if(son[x][c=s[i]-'A'])x=son[x][c];else return 0;
	return size[x];
}
int main(){
	scanf("%d%s",&m,s);
	last=S=++cnt;n=strlen(s);
	for(i=0;i<n;i++)add(i);
	while(m--){
		scanf("%s%s",ch,s);n=strlen(s);
		DecodeWithMask(mask);
		if(ch[0]=='Q'){
			printf("%d\n",ans=query());
			mask^=ans;
		}else for(i=0;i<n;i++)add(i);
	}
}

BZOJ3998:第K大子串,维护val和sum

#include<cstdio>
#include<cstring>
#define N 1111111
int n,S,last,i,cnt,T,k,c,p,q,np,nq,j,v[N],wa[N],son[N][26],fa[N],step[N],val[N],sum[N];char s[N];
void add(int x){
	c=s[x]-'a';p=last;np=last=++cnt;step[np]=step[p]+1;
	for(val[np]=1;p&&!son[p][c];p=fa[p])son[p][c]=np;
	if(!p)fa[np]=S;else{
		q=son[p][c];
		if(step[p]+1==step[q])fa[np]=q;else{
			nq=++cnt;step[nq]=step[p]+1;
			memcpy(son[nq],son[q],sizeof son[q]);
			fa[nq]=fa[q];fa[q]=fa[np]=nq;
			for(;son[p][c]==q;p=fa[p])son[p][c]=nq;
		}
	}
}
int main(){
	scanf("%s",s);n=strlen(s);
	S=last=++cnt;
	for(i=0;i<n;i++)add(i);
	scanf("%d%d",&T,&k);
	for(i=1;i<=cnt;i++)v[step[i]]++;
	for(i=1;i<=n;i++)v[i]+=v[i-1];
	for(i=cnt;i;i--)wa[v[step[i]]--]=i;
	for(i=cnt;i;i--){
		c=wa[i];
		if(T)val[fa[c]]+=val[c];else val[c]=1;
	}
	for(val[1]=0,i=cnt;i;i--){
		c=wa[i];sum[c]=val[c];
		for(j=0;j<26;j++)sum[c]+=sum[son[c][j]];
	}
	if(sum[1]<k)return puts("-1"),0;
    for(i=S;k>val[i];){
        for(k-=val[i],j=0;j<26;j++)
        if(sum[son[i][j]]<k)k-=sum[son[i][j]];
        else{putchar(j+'a');i=son[i][j];break;}
    }
}

BZOJ2780 广义的后缀自动机(多串后缀自动机),似乎就是每次从根开始加,加的时候如果该节点已经有了就用原来的,用map维护son[],建出广义后缀树,得到DFS序,然后树状数组离线处理所有询问

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#define N 444444
using namespace std;
map<int,int>son[N];
int n,m,cnt,S,last,tot,dfn,tmp,p,q,np,nq,c,i,j,k,y,fa[N],step[N],w[N],vis[N],ans[N];
struct EG{int l,r,id;}eg[N];char s[N];bool ff;
bool cmp(EG a,EG b){return a.r<b.r;}
void add(int x,int z){for(;x<=cnt;x+=x&-x)w[x]+=z;}
int query(int x){if(!x)return 0;tmp=0;for(;x;x-=x&-x)tmp+=w[x];return tmp;}
struct Suffic_Tree{
	int first[N],next[N],last[N],st[N],ed[N],pos[N],tot,dfn;
	void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;}
	void dfs(int x){
		st[x]=++dfn;pos[dfn]=x;
		for(int i=first[x];i;i=next[i])dfs(last[i]);
		ed[x]=dfn;
	}
}sft,belong;
void ad(int x,int id){
	c=s[x]-'a';p=last;np=son[p][c];
	if(np){
		if(step[np]==step[p]+1)last=np;else{
			nq=++cnt;step[nq]=step[p]+1;
			fa[nq]=fa[np];fa[np]=nq;
			son[nq]=son[np];
			for(;p&&son[p][c]==np;p=fa[p])son[p][c]=nq;
			last=nq;
		}
	}else{
		np=last=++cnt;step[np]=step[p]+1;
		for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
		if(!p)fa[np]=S;else{
			q=son[p][c];
			if(step[p]+1==step[q])fa[np]=q;else{
				nq=++cnt;step[nq]=step[p]+1;
				son[nq]=son[q];
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
			}
		}
		last=np;
	}
	belong.ins(last,id);
}
int main(){
	scanf("%d%d",&n,&m);
	S=++cnt;
	for(i=1;i<=n;i++){
		scanf("%s",s);last=S;
		for(j=0;s[j];j++)ad(j,i);
	}
	for(i=2;i<=cnt;i++)sft.ins(fa[i],i);
	sft.dfs(1);
	for(i=1;i<=m;i++){
		scanf("%s",s);ff=1;
		for(p=1,j=0;s[j];j++){
			c=s[j]-'a';
			if(!son[p][c]){ff=0;break;}
			p=son[p][c];
		}
		eg[i].id=i;
		if(ff)eg[i].l=sft.st[p],eg[i].r=sft.ed[p];else eg[i].l=eg[i].r=-1;
	}
	sort(eg+1,eg+m+1,cmp);
	for(k=1;k<=m&&eg[k].r==-1;k++);
	for(j=1;j<=cnt;j++){
		for(i=belong.first[sft.pos[j]];i;i=belong.next[i]){
			y=belong.last[i];add(j,1);
			if(vis[y])add(vis[y],-1);
			vis[y]=j;
		}
		for(;eg[k].r==j&&k<=m;k++)ans[eg[k].id]=query(eg[k].r)-query(eg[k].l-1);
	}
	for(i=1;i<=m;i++)printf("%d\n",ans[i]);
}

BZOJ3926:由于只有20个叶子节点,对每个叶子节点做一遍后缀自动机就行了,似乎不一定要广义的,答案就是Σstep[i]-step[fa[i]] 哎,ZJOI考这种1K代码的题,我当初却不会

#include<cstdio>
#include<cstring>
#define N 1111111
int c,n,cnt,tot,p,q,np,nq,S,i,x,y,color[N],first[N],step[N],a[N][11],fa[N],du[N],next[N],last[N],now[N];
long long ans;
void ins(int x,int y){last[++tot]=y;next[tot]=first[x];first[x]=tot;du[x]++;}
int add(int p,int x){
	np=a[p][x];if(np&&step[np]==step[p]+1)return np;
	step[np=++cnt]=step[p]+1;
	for(;p&&!a[p][x];p=fa[p])a[p][x]=np;
	if(!p)fa[np]=S;else{
		q=a[p][x];
		if(step[p]+1==step[q])fa[np]=q;else{
			step[nq=++cnt]=step[p]+1;
			memcpy(a[nq],a[q],sizeof a[q]);
			fa[nq]=fa[q];fa[q]=fa[np]=nq;
			for(;p&&a[p][x]==q;p=fa[p])a[p][x]=nq;
		}
	}
	return np;
}
void dfs(int x,int fa,int p){
	int t=add(p,color[x]);
	for(int i=first[x];i;i=next[i])if(last[i]!=fa)dfs(last[i],x,t);
}
int main(){
	scanf("%d%d",&n,&c);
	now[0]=S=++cnt;
	for(i=1;i<=n;i++)scanf("%d",&color[i]);
	for(i=1;i<n;i++)scanf("%d%d",&x,&y),ins(x,y),ins(y,x);
	for(i=1;i<=n;i++)if(du[i]==1)dfs(i,0,1);
	for(i=1;i<=cnt;i++)ans+=(long long)step[i]-(long long)step[fa[i]];
	printf("%lld",ans);
}

【NOI2015】【BZOJ4199】品酒大会 用后缀自动机建出后缀树,然后就变成了后缀树裸题。。这么简单的题我当时却不会QAQ

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 600006
#define inf 2e18
using namespace std;
long long n,m,cnt,S,last,tot,now,tmp,p,q,np,nq,c,i,j,y,son[N][26],fa[N],step[N],a[N],to[N],mi1[N],mi2[N],ma1[N],ma2[N],sz[N],la[N],ne[N],fi[N],va[N],ans[N],mav[N],nx[N];
char s[N];bool vis[N];
void insert(long long x,long long y,long long z){la[++tot]=y;ne[tot]=fi[x];va[tot]=z;fi[x]=tot;}
void add(long long x){
    c=s[x]-'a';p=last;step[np=last=++cnt]=step[p]+1;to[np]=i;
    for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
    if(!p)fa[np]=S;else{
        q=son[p][c];
        if(step[p]+1==step[q])fa[np]=q;else{
            nq=++cnt;step[nq]=step[p]+1;
            memcpy(son[nq],son[q],sizeof son[q]);
            fa[nq]=fa[q];fa[q]=fa[np]=nq;
            for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
        }
    }
}
void dfs(long long x,long long high){
    if(to[x])ma1[x]=mi1[x]=a[to[x]],sz[x]=1;else ma1[x]=-inf,mi1[x]=inf,sz[x]=0;
    ma2[x]=-inf;mi2[x]=inf;
    for(long long i=fi[x];i;i=ne[i]){
        long long y=la[i];
        dfs(y,high+va[i]);
        if(ma1[y]>ma1[x]){
            ma2[x]=ma1[x];ma1[x]=ma1[y];
            if(ma2[y]>ma2[x])ma2[x]=ma2[y];
        }else if(ma1[y]>ma2[x])ma2[x]=ma1[y];
        if(mi1[y]<mi1[x]){
            mi2[x]=mi1[x];mi1[x]=mi1[y];
            if(mi2[y]<mi2[x])mi2[x]=mi2[y];
        }else if(mi1[y]<mi2[x])mi2[x]=mi1[y];
        sz[x]+=sz[y];nx[x]+=nx[y];
    }
    now=-inf;tmp=(sz[x]*(sz[x]-1))/2;
    if(sz[x]>=4)now=max(max(ma1[x]*ma2[x],mi1[x]*mi2[x]),max(ma1[x]*mi2[x],ma2[x]*mi1[x]));
    else if(sz[x]>=3)now=max(max(ma1[x]*ma2[x],mi1[x]*mi2[x]),ma1[x]*mi1[x]);
    else if(sz[x]>=2)now=ma1[x]*ma2[x];
    if(now!=inf)ans[high]+=tmp-nx[x],mav[high]=max(mav[high],now);
    nx[x]+=tmp-nx[x];
}
int main(){
    scanf("%lld",&n);scanf("%s",s+1);
    for(S=last=++cnt,i=n;i;i--)add(i);
    for(vis[S]=i=1;i<=cnt;i++)
        if(to[i]&&!vis[i])for(j=i;!vis[j];vis[j]=1,j=fa[j])insert(fa[j],j,step[j]-step[fa[j]]);
    for(i=0;i<=n;i++)mav[i]=-inf;
    for(i=1;i<=n;i++)scanf("%lld",&a[i]);
    dfs(1,0);
    for(i=n-1;i>=0;i--)ans[i]=ans[i]+ans[i+1],mav[i]=max(mav[i],mav[i+1]);
    for(i=0;i<n;i++){
        if(mav[i]==-inf)mav[i]=0;
        printf("%lld %lld\n",ans[i],mav[i]);
    }
}

2015多校集训第5场T1:毛主力的周圆圆

把A串正着建后缀自动机,B串反着建后缀自动机,然后把B串所有对应字符的节点控制的节点弄出来,统计出每种字符出现的次数,然后在A的后缀自动机上统计1-cnt,答案为step[i]-step[fa[i]]*(1(表示只有A)+dp[j](0<=j<26且!son[i][j])(表示后面接字符j)

#include<cstdio>
#include<cstring>
#define frn(i,n) for(int i=1;i<=n;i++)
#define fr(i,a,b) for(int i=a;i<=b;i++)
#define drn(i,n) for(int i=n;i;i--)
#define CL(a) memset(a,0,sizeof(a))
#define N 200000
typedef unsigned long long LL;
int T,n,m,i,j;char s[N];LL ans,dp[27];bool vis[N];
struct SAM{
	int S,p,q,np,nq,last,cnt,son[N][26],fa[N],step[N],to[N];
	void init(){
		S=last=cnt=1;
		memset(to,-1,sizeof(to));
		CL(son);CL(step);CL(fa);
		step[0]=-1;
	}
	void add(int c){
		p=last;last=np=++cnt;step[np]=step[p]+1;to[np]=c;
		for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
		if(!p)fa[np]=S;else{
			q=son[p][c];
			if(step[p]+1==step[q])fa[np]=q;else{
				nq=++cnt;step[nq]=step[p]+1;
				memcpy(son[nq],son[q],sizeof son[q]);
				fa[nq]=fa[q];fa[q]=fa[np]=nq;
				for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
			}
		}
	}
}A,B;
int main(){
	scanf("%d",&T);
	while(T--){
		ans=0;A.init();B.init();CL(dp);CL(vis);
		scanf("%s",s+1);n=strlen(s+1);frn(i,n)A.add(s[i]-'a');
		scanf("%s",s+1);m=strlen(s+1);drn(i,m)B.add(s[i]-'a');
		for(vis[B.S]=i=1;i<=B.cnt;i++)if(B.to[i]>=0&&!vis[i])
			for(j=i;!vis[j];vis[j]=1,j=B.fa[j])if(B.to[B.fa[j]]==-1)B.to[B.fa[j]]=B.to[i];else break;
		fr(i,2,B.cnt)dp[B.to[i]]+=(LL)(B.step[i]-B.step[B.fa[i]]);
		frn(i,A.cnt){
			LL num=(LL)(A.step[i]-A.step[A.fa[i]]);
			ans+=num;
			for(int j=0;j<26;j++)if(!A.son[i][j])ans+=num*dp[j];
		}
		printf("%I64u\n",ans);
	}
}

ZHOJ2090 对A串建后缀自动机,求出每种状态的RIGHT集合大小,然后B串在SAM上走,统计出当前的最大公共前缀k,如果k>=L那么ans+=(k-max(L,step[fa[p]]+1)+1)*sz[p],但发现如果要得到正确的答案还要不断走fa[p],但如果每次暴力走fa[p]会T,可以在fa[p]上打一个标记,最后再处理一遍,就可以达到线性复杂度了

#include<cstdio>
#include<cstring>
#include<algorithm>
#define N 200100
#define CL(a) memset(a,0,sizeof(a))
using namespace std;typedef long long LL;LL ans;
int n,i,c,p,q,np,nq,la,tmp,cnt,now,L,S,son[N][26],f[N],st[N],fa[N],sz[N],b[N],pos[N];char s[N];
void add(int c,int w){
	for(p=la,np=son[p][c],st[np=la=++cnt]=st[p]+1;p&&!son[p][c];p=fa[p])son[p][c]=np;
	if(!p)fa[np]=S;else if(st[p]+1==st[q=son[p][c]])fa[np]=q;else{
		nq=++cnt;st[nq]=st[p]+1;memcpy(son[nq],son[q],sizeof son[q]);
		for(fa[nq]=fa[q],fa[q]=fa[np]=nq;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
	}
}
int main(){
	for(;scanf("%d",&L)!=-1;printf("%lld\n",ans)){
		CL(sz);CL(son);CL(fa);CL(st);CL(f);CL(b);ans=cnt=0;
		for(scanf("%s",s),n=strlen(s),S=la=++cnt,i=0;i<n;i++)add(s[i]-'a',1);
		for(i=1;i<=cnt;i++)b[st[i]]++;
		for(i=1;i<=n;i++)b[i]+=b[i-1];
		for(i=1;i<=cnt;i++)pos[b[st[i]]--]=i;
		for(i=0,p=1;i<n;i++)sz[p=son[p][s[i]-'a']]++;
		for(i=cnt;i;i--)sz[fa[pos[i]]]+=sz[pos[i]];
		for(scanf("%s",s),n=strlen(s),p=1,tmp=i=0;i<n;i++){
			if(son[p][c=s[i]-'a'])p=son[p][c],tmp++;else{
				for(;!son[p][c]&&p;p=fa[p]);
				if(!p)p=1,tmp=0;else tmp=st[p]+1,p=son[p][c];
			}
			if(tmp>=L)ans+=(LL)(tmp-max(L,st[fa[p]]+1)+1)*sz[p],f[fa[p]]+=st[fa[p]]>=L;
		}
		for(i=cnt;i;i--){
			ans+=(LL)f[p=pos[i]]*(st[p]-max(L,st[fa[p]]+1)+1)*sz[p];
			if(st[fa[p]]>=L)f[fa[p]]+=f[p];
		}
	}
}

【CTSC2012】BZOJ2806 Cheat 先建出广义自动机,然后匹配串在上面跑,记录当前能取到的最长匹配w,二分答案lim,那么f[i]=max(f[i-1],f[j]+i-j)(i-w<=j<=i-lim),然后单调队列转移就可以啦

#include<bits/stdc++.h>
#define N 5555555
using namespace std;char s[N];int n,m,S,la,i,j,u,w,l,r,h,t,mid,ans,cnt,mx,p,q,np,nq,c[N][2],st[N],fa[N],f[N],Q[N],v[N];
void add(int w){
	p=la;np=c[p][w];
	if(!np||st[np]!=st[p]+1){
		for(st[np=++cnt]=st[la]+1;p&&!c[p][w];p=fa[p])c[p][w]=np;
		if(!p)fa[np]=1;else if(q=c[p][w],st[p]+1==st[q])fa[np]=q;else
			for(st[nq=++cnt]=st[p]+1,c[nq][0]=c[q][0],c[nq][1]=c[q][1],fa[nq]=fa[q],fa[q]=fa[np]=nq;p&&c[p][w]==q;p=fa[p])c[p][w]=nq;
	}la=np;
}
bool ok(int z){
	for(h=1,t=0,i=1;i<=u;i++)if(i<z)f[i]=0;else{
		for(f[i]=f[i-1],p=i-z;h<=t&&f[p]-p>=f[Q[t]]-Q[t];t--);
		for(Q[++t]=p;h<=t&&Q[h]<i-v[i];h++);
		if(h<=t)f[i]=max(f[i],f[Q[h]]-Q[h]+i);
	}
	return f[u]*10>=u*9;
}
int main(){
	for(scanf("%d%d",&n,&m),cnt=S=i=1;i<=m;i++)for(scanf("%s",s),la=1,j=0;s[j];j++)add(s[j]-'0');
	for(;n--;printf("%d\n",ans)){
		for(scanf("%s",s),u=strlen(s),p=1,i=mx=0;i<u;v[++i]=mx){
			for(w=s[i]-'0';!c[p][w]&&p;p=fa[p]);
			if(!p)p=1,mx=0;else mx=min(st[p],mx)+1,p=c[p][w];
		}
		for(l=0,r=u;l<=r;)if(ok(mid=l+r>>1))ans=mid,l=mid+1;else r=mid-1;
	}
}

然后发现可以用后缀树O(n)构造出后缀数组,当然常数是26,用map优化一下常数就是rlogr,r为该点实际儿子个数,比后缀数组DC3算法不知道高到哪去了,这样再也不怕后缀数组写炸了

#include<cstdio>
#include<cstring>
#define N 600006
using namespace std;
int n,m,cnt,S,last,tot,now,tmp,p,q,np,nq,c,i,j,k,y,top,pos,sa[N],rank[N],len[N][26],ch[N][26],son[N][26],fa[N],step[N],to[N],sz[N],las[N],ne[N],fi[N],va[N],height[N];
char s[N];bool vis[N];
void insert(int x,int y,int z){las[++tot]=y;ne[tot]=fi[x];va[tot]=z;fi[x]=tot;}
void add(int x){
    c=s[x]-'a';p=last;step[np=last=++cnt]=step[p]+1;to[np]=i;
    for(;p&&!son[p][c];p=fa[p])son[p][c]=np;
    if(!p)fa[np]=S;else{
        q=son[p][c];
        if(step[p]+1==step[q])fa[np]=q;else{
            nq=++cnt;step[nq]=step[p]+1;
            memcpy(son[nq],son[q],sizeof son[q]);
            fa[nq]=fa[q];fa[q]=fa[np]=nq;
            for(;p&&son[p][c]==q;p=fa[p])son[p][c]=nq;
        }
    }
}
void dfs(int x,int la,int high){
    to[x]?sz[x]=1,sa[++top]=to[x]:sz[x]=0;
    for(int i=0;i<26;i++)if(ch[x][i])dfs(ch[x][i],x,high+len[x][i]),sz[x]+=sz[ch[x][i]];
}
int main(){
    scanf("%s",s+1);n=strlen(s+1);
    for(S=last=++cnt,i=n;i;i--)add(i);
    for(vis[S]=i=1;i<=cnt;i++)
        if(to[i]&&!vis[i])for(pos=n,j=i;!vis[j];vis[j]=1,j=fa[j],pos--)
			pos-=step[j]-step[fa[j]]-1,ch[fa[j]][s[pos]-'a']=j,len[fa[j]][s[pos]-'a']=step[j]-step[fa[j]],insert(fa[j],j,step[j]-step[fa[j]]);
    dfs(1,0,0);
	for(i=1;i<=n;i++)rank[sa[i]]=i;
	for(i=1;i<=n;i++)printf("%d ",sa[i]);puts("");
	for(i=1;i<=n;height[rank[i++]]=k)
    	for(k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);
    for(i=2;i<=n;i++)printf("%d ",height[i]);
}

 

事实证明还是要26的常数比较好,map常数似乎也挺大的

BZOJ4032 建出两个串的后缀自动机和序列自动机,然后BFS,用(i,j)表示在自动机A上走到i,自动机B上走到j。如果有某点A不能走而B能走则得到答案。

#include<bits/stdc++.h>
#define N 4004
using namespace std;char A[N],B[N];int h,t,v[N][N];
struct P{int x,y;};queue<P>Q;
struct W{
	int p,np,q,nq,cnt,c[N][26],F[N],L[N];
	void add(int x){
		for(p=np,L[np=++cnt]=L[p]+1;p&&!c[p][x];p=F[p])c[p][x]=np;
		if(!p)F[np]=1;else if(L[p]+1==L[q=c[p][x]])F[np]=q;else for(L[nq=++cnt]=L[p]+1,memcpy(c[nq],c[q],sizeof c[q]),F[nq]=F[q],F[q]=F[np]=nq;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
	}
	void ins(int x){
		int i=0,o=++cnt;
		for(;i<26;i++)for(p=L[i];p&&!c[p][x];p=F[p])c[p][x]=o;
		F[o]=L[x];L[x]=o;
	}
	void I(char *s,int lx){
		int i;np=1;cnt=1;
		if(lx)for(i=0;s[i];i++)add(s[i]-'a');else{
			for(i=0;i<26;i++)L[i]=1;for(i=0;s[i];i++)ins(s[i]-'a');
		}
	}
}A1,A2,B1,B2;
int bfs(W A,W B){
	for(memset(v,0,sizeof(v)),v[1][1]=1;!Q.empty();Q.pop());Q.push(P{1,1});
	for(;!Q.empty();){
		int i,x=Q.front().x,y=Q.front().y,X,Y;Q.pop();
		for(i=0;i<26;i++){
			X=A.c[x][i];Y=B.c[y][i];if(!X)continue;if(!Y)return v[x][y];
			if(!v[X][Y])v[X][Y]=v[x][y]+1,Q.push(P{X,Y});
		}
	}return -1;
}
int main(){scanf("%s%s",A,B);A1.I(A,1);A2.I(A,0);B1.I(B,1);B2.I(B,0);printf("%d\n%d\n%d\n%d",bfs(A1,B1),bfs(A1,B2),bfs(A2,B1),bfs(A2,B2));}

BZOJ3413 建出后缀树,然后每个串进去匹配。先找到能匹配的标号最小的后缀,然后往根跳,每次给答案加上长度差*子树内小于该标号的个数。于是可以按DFS序从小到大以标号为关键字建主席树,来完成这个过程。

#include<bits/stdc++.h>
#define N 200200
using namespace std;char s[N],b[N];bool v[N];int n,m,i,j,p,o,w,x,fl,B,np,q,nq,id,di,cnt,tot,ans,V[N],to[N],F[N],c[N][10],E[N],st[N],ed[N],fir[N],ne[N],va[N],la[N],T[N],sz[N*20],L[N*20],R[N*20];
void ins(int x,int y,int z){la[++tot]=y;va[tot]=z;ne[tot]=fir[x];fir[x]=tot;}
void add(int x){
	for(p=np,E[np=++cnt]=E[p]+1,to[np]=i;p&&!c[p][x];p=F[p])c[p][x]=np;
	if(!p)F[np]=1;else if(E[p]+1==E[q=c[p][x]])F[np]=q;else for(E[nq=++cnt]=E[p]+1,F[nq]=F[q],memcpy(c[nq],c[q],sizeof c[q]),F[q]=F[np]=nq;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
}
void A(int w){
	for(p=np,E[np=++cnt]=E[p]+1,to[np]=i;p&&!c[p][w];p=F[p])c[p][w]=np;
	if(!p)F[np]=1;else if(E[q=c[p][w]]==E[p]+1)F[np]=q;else for(E[nq=++cnt]=E[p]+1,memcpy(c[nq],c[q],sizeof(c[q])),F[nq]=F[q],F[q]=F[np]=nq;p&&c[p][w]==q;p=F[p])c[p][w]=nq;
}
void dfs(int x){st[x]=++id;V[id]=to[x]?n-E[x]:-1;for(int i=fir[x];i;i=ne[i])dfs(la[i]);ed[x]=id;}
bool find(){
	int w=1,u,i,j,ff=1;x=1;
	for(fl=0;w<=B&&ff;)for(ff=0,i=fir[x];i;i=ne[i])if(s[va[i]]==b[w]){
		for(fl=j=0;j<min(E[la[i]]-E[x],B-w+1);fl++,j++)if(s[va[i]+j]!=b[w+j])return x=la[i],0;
		w+=E[la[i]]-E[x];x=la[i];ff=1;break;
	}return ff;
}
void cha(int y,int&x,int l,int r,int k){
	sz[x=++di]=sz[y]+1;L[x]=L[y];R[x]=R[y];if(l==r)return;int mid=l+r>>1;
	if(k<=mid)cha(L[y],L[x],l,mid,k);else cha(R[y],R[x],mid+1,r,k);
}
int gm(int x,int y){
	int l=0,r=n,mid;
	for(;l<r;)if(mid=l+r>>1,sz[L[y]]-sz[L[x]])x=L[x],y=L[y],r=mid;else x=R[x],y=R[y],l=mid+1;
	return l;
}
int ask(int k,int l,int r,int x){
	if(!k)return 0;if(r<=x)return sz[k];int mid=l+r>>1,o=ask(L[k],l,mid,x);
	if(x>mid)o+=ask(R[k],mid+1,r,x);return o;
}
int main(){
	for(scanf("%d%s",&n,s+1),np=++cnt,i=n;i;i--)A(s[i]-'0');
	for(v[1]=i=1;i<=cnt;i++)if(to[i])for(p=n,j=i;!v[j];j=F[j])p-=E[j]-E[F[j]],v[j]=1,ins(F[j],j,p+1);
	for(dfs(1),i=1;i<=id;i++)if(V[i]>=0)cha(T[i-1],T[i],0,n,V[i]);else T[i]=T[i-1];
	for(scanf("%d",&m);m--;printf("%d\n",ans)){
		scanf("%s",b+1);B=strlen(b+1);ans=w=find()?gm(T[st[x]-1],T[ed[x]]):n;
		for(ans+=fl*(ask(T[ed[x]],0,n,w)-ask(T[st[x]-1],0,n,w)),x=F[x];x;x=F[x])ans+=(E[x]-E[F[x]])*(ask(T[ed[x]],0,n,w)-ask(T[st[x]-1],0,n,w));
	}
}

BZOJ4310 二分第K大的串,然后从后往前判断,一旦一个后缀不合法就要分段,判断的方法可以求出两个串的LCP后判。不会SA写个SAM转后缀树O(nlgn)预处理O(1)询问LCA得到答案。时间复杂度O(nlgn),被SA虐飞TAT

#include<bits/stdc++.h>
#define N 400100
using namespace std;typedef long long LL;char s[N],W[N];bool v[N];LL A,L,R,mid,S[N];
int n,K,k,i,j,x,u,p,np,q,nq,o,id,cnt,d[N],ot[N],gl[N],ST[N][26],G[N][20],c[N][26],C[N][26],st[N],F[N],V[N],pos[N],to[N];
void add(int x){
	for(p=np,st[np=++cnt]=st[p]+1,to[np]=i,ot[i]=np;p&&!c[p][x];p=F[p])c[p][x]=np;
	if(!p)F[np]=1;else if(st[p]+1==st[q=c[p][x]])F[np]=q;else for(st[nq=++cnt]=st[p]+1,F[nq]=F[q],memcpy(c[nq],c[q],sizeof c[q]),F[q]=F[np]=nq;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
}
void dfs(int x,int fa){
	V[x]=S[x]=st[x]-st[fa];G[pos[x]=++id][0]=st[x];
	for(int i=0,y;i<26;i++)if(y=C[x][i])dfs(y,x),S[x]+=S[y],G[++id][0]=st[x];
}
int dis(int x,int y){int t;x=pos[x];y=pos[y];if(x>y)swap(x,y);t=gl[y-x+1];return min(G[x][t],G[y-(1<<t)+1][t]);}
int kth(LL k){
	int i=1,j,u;o=0;
	for(;k>V[i];)for(k-=V[i],j=0;j<26;j++)if(S[C[i][j]]<k)k-=S[C[i][j]];else{
		for(u=0;u<(int)min((LL)st[C[i][j]]-st[i],k);u++)W[++o]=s[ST[i][j]+u];
		i=C[i][j];break;
	}return i;
}
bool ask(int l,int r){int t=dis(ot[l],u);return t>=min(r-l+1,o)?r-l+1<=o:s[l+t]<=W[t+1];}
bool ok(){
	int i,j,k=0;
	for(i=n;i;i=j,k++){for(j=i;j;j--)if(!ask(j,i))break;if(j==i)return 0;}
	return k<=K;
}
int main(){
	for(scanf("%d%s",&K,s+1),n=strlen(s+1),np=cnt=1,i=n;i;i--)add(s[i]-'a');
	for(v[1]=i=1;i<=cnt;i++)if(to[i])for(p=n,j=i;!v[j];j=F[j])p-=st[j]-st[F[j]],v[j]=1,C[F[j]][s[p+1]-'a']=j,ST[F[j]][s[p+1]-'a']=p+1;
	for(dfs(1,0),i=2;i<=id;i++)gl[i]=gl[i>>1]+1;
    for(j=1;j<=gl[id];j++)for(i=1;i+(1<<j)-1<=id;i++)G[i][j]=min(G[i][j-1],G[i+(1<<j-1)][j-1]);
	for(L=0,R=S[1];L<=R;)if(u=kth(mid=L+R>>1),ok())R=(A=mid)-1;else L=mid+1;
	for(kth(A),i=1;i<=o;i++)putchar(W[i]);
}

BZOJ4556 后缀自动机+二分答案+倍增+线段树合并

#include<bits/stdc++.h>
#define N 200200
using namespace std;char s[N];int n,m,x,i,j,p,np,q,nq,W,id,A,B,C,D,l,r,md,F[N],f[N][17],c[N][26],ps[N],b[N],E[N],T[N],to[N],L[N*20],R[N*20];
void ins(int&x,int l,int r,int z){x=++id;if(l==r)return;int md=l+r>>1;z<=md?ins(L[x],l,md,z):ins(R[x],md+1,r,z);}
int mg(int x,int y){if(!x||!y)return x+y;int z=++id;L[z]=mg(L[x],L[y]);R[z]=mg(R[x],R[y]);return z;}
int qu(int k,int l,int r,int x,int y){if(!k)return 0;if(x<=l&&r<=y)return 1;int md=l+r>>1;return x<=md&&qu(L[k],l,md,x,y)||y>md&&qu(R[k],md+1,r,x,y);}
void AD(int x){
	for(p=np,E[np=++W]=E[p]+1,ins(T[np],1,n,i),to[i]=np;p&&!c[p][x];p=F[p])c[p][x]=np;
	if(!p)F[np]=1;else if(E[p]+1==E[q=c[p][x]])F[np]=q;else for(E[nq=++W]=E[p]+1,F[nq]=F[q],memcpy(c[nq],c[q],sizeof c[q]),F[q]=F[np]=nq;p&&c[p][x]==q;p=F[p])c[p][x]=nq;
}
int ok(int x,int a,int b,int p){for(int i=16;~i;i--)if(x<=E[f[p][i]])p=f[p][i];return qu(T[p],1,n,a,b-x+1);}
int main(){
	for(scanf("%d%d%s",&n,&m,s+1),np=++W,i=n;i;i--)AD(s[i]-'a');
	for(i=1;i<=W;i++)b[E[i]]++;for(i=1;i<=n;i++)b[i]+=b[i-1];
	for(i=1;i<=W;i++)ps[b[E[i]]--]=i;for(i=W;i;i--)T[F[ps[i]]]=mg(T[F[ps[i]]],T[ps[i]]);
	for(i=1;i<=W;i++)for(x=ps[i],f[x][0]=F[x],j=1;j<=16;j++)f[x][j]=f[f[x][j-1]][j-1];
	for(;m--;printf("%d\n",l))for(scanf("%d%d%d%d",&A,&B,&C,&D),l=0,r=min(B-A,D-C)+2;l+1<r;)if(ok(md=l+r>>1,A,B,to[C]))l=md;else r=md;
}

BZOJ4545 后缀自动机+有向LCT

#include<bits/stdc++.h>
#define N 200100
using namespace std;bool rv[N];long long an;char s[N];
int n,m,o,i,x,y,rt,z,T,q,np,nq,tot,cnt,fir[N],la[N],ne[N],va[N],e[N][2],c[N][3],F[N],fa[N],V[N],st[N],lz[N],Q[N],E[N],W[N];
void ins(int x,int y,int z){la[++tot]=y;ne[tot]=fir[x];va[tot]=z;fir[x]=tot;}
bool ir(int x){return e[fa[x]][0]!=x&&e[fa[x]][1]!=x;}
void rev(int x){swap(e[x][0],e[x][1]);rv[x]^=1;}
void AD(int x,int z){lz[x]+=z;V[x]+=z;}
void pd(int x){
	if(rv[x])rev(e[x][0]),rev(e[x][1]),rv[x]=0;
	if(lz[x])AD(e[x][0],lz[x]),AD(e[x][1],lz[x]),lz[x]=0;
}
void ps(int x){}
void R(int x){
    int y=fa[x],k=e[y][0]==x;
    fa[e[y][!k]=e[x][k]]=y;
    fa[x]=fa[y];if(!ir(y))e[fa[y]][e[fa[y]][1]==y]=x;
    fa[e[x][k]=y]=x;ps(y);
}
void dw(int x){if(!ir(x))dw(fa[x]);pd(x);}
void sy(int x){for(dw(x);!ir(x);R(x))if(!ir(fa[x]))R(e[fa[x]][0]==x^e[fa[fa[x]]][0]==fa[x]?x:fa[x]);ps(x);}
void acs(int x){for(int y=0;x;ps(x),y=x,x=fa[x])sy(x),e[x][1]=y;}
void lk(int x,int y){fa[x]=y;acs(y);sy(y);AD(y,V[x]);}
void ct(int x){acs(x);sy(x);AD(e[x][0],-V[x]);fa[e[x][0]]=0;e[x][0]=0;}
int add(int p,int x){
	for(st[np=++cnt]=st[p]+1;p&&!c[p][x];p=F[p])c[p][x]=np;V[np]=1;
	if(!p)F[np]=1,lk(np,1);else if(st[p]+1==st[q=c[p][x]])F[np]=q,lk(np,q);else{
		st[nq=++cnt]=st[p]+1,memcpy(c[nq],c[q],sizeof c[q]);
		F[nq]=F[q];lk(nq,F[q]);F[np]=F[q]=nq;ct(q);lk(q,nq);lk(np,nq);
		for(;c[p][x]==q;p=F[p])c[p][x]=nq;
	}
	an+=st[np]-st[F[np]];return np;
}
void dfs(int x,int fa,int V){
	int i,y,w=add(W[fa],V);W[x]=w;
	for(i=fir[x];i;i=ne[i])if(la[i]!=fa)dfs(la[i],x,va[i]);
}
int main(){
	for(scanf("%d%d",&x,&n),cnt=i=1;i<n;i++)scanf("%d%d%s",&x,&y,s),ins(x,y,s[0]-'a'),ins(y,x,s[0]-'a');
	for(i=fir[1],W[1]=1;i;i=ne[i])dfs(la[i],1,va[i]);
	for(scanf("%d",&m);m--;){
		scanf("%d",&o);
		if(o==1)printf("%lld\n",an);else if(o==2){
			for(scanf("%d%d",&rt,&z),T=0,i=1;i<z;i++){
				scanf("%d%d%s",&x,&y,s),ins(x,y,s[0]-'a'),ins(y,x,s[0]-'a');
				if(x==rt||y==rt)Q[++T]=x^y^rt,E[T]=s[0]-'a';
			}
			for(i=1;i<=T;i++)dfs(Q[i],rt,E[i]);
		}else{
			for(scanf("%s",s),z=strlen(s),x=1,i=0;i<z;i++)if(x)x=c[x][s[i]-'a'];
			if(x)acs(x),sy(x),printf("%d\n",V[x]);else puts("0");
		}
	}
}

待做:BZOJ1396、3277=3473

三、Manacher

看了看论文,稍微学了下Manacher,感觉并没有什么卵用

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=110010;//求最长回文子串
int n,i,ans,l,p,mx,r[N];char ma[N*2],s[N];
int main(){
	scanf("%s",s);n=strlen(s);
	ma[l++]='$';ma[l++]='#';
	for(i=0;i<n;i++)ma[l++]=s[i],ma[l++]='#';
	for(i=0;i<l;i++){
		r[i]=mx>i?min(r[2*p-i],mx-i):1;
		for(;ma[i+r[i]]==ma[i-r[i]];r[i]++);
		if(i+r[i]>mx)mx=i+r[i],p=i;
	}
	for(int i=0;i<2*n+2;i++)ans=max(ans,r[i]-1);
	printf("%d\n",ans);
}

感觉还是有点用的,比如说求最长双回文串或最长1.5回文串,打多校时候碰到了,需要Manacher后用set维护

四、回文自动机

然后看了看回文自动机,不知道比Manacher高到哪去了。。回文自动机可以O(n)求本质不同的回文串的个数和每个回文串出现的次数,而且代码非常短,比后缀自动机还短。。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 300006
using namespace std;
char s[N];int i,now,p,cnt,n,sz[N],fa[N],len[N],ch[N][26];long long ans;
void add(int c,int n){
	while(s[n-len[p]-1]!=s[n])p=fa[p];//失配后找一个尽量最长的
	if(!ch[p][c]){//如果这个回文串没有出现过,说明出现了一个新的本质不同的回文串
		int now=++cnt,k=fa[p];//新建节点
		len[now]=len[p]+2;
		while(s[n-len[k]-1]!=s[n])k=fa[k];//构建失败指针
		fa[now]=ch[k][c];ch[p][c]=now;
	}
	p=ch[p][c];sz[p]++;
}
int main(){
	cnt=1;fa[0]=fa[1]=1;len[1]=-1;//开头放一个字符集中没有的字符,减少特判
	scanf("%s",s+1);n=strlen(s+1);
	for(i=1;i<=n;i++)add(s[i]-'a',i);
	for(i=cnt;i;i--)sz[fa[i]]+=sz[i],ans=max(ans,(long long)sz[i]*len[i]);
	printf("%lld",ans);
}

 

Avatar_small
orz hhw 说:
2015年7月29日 13:53

尛当场A T2的后缀数组大爷

Avatar_small
nbdhhzh 说:
2015年7月30日 17:04

为什么不使用神器后缀树呢?

Avatar_small
hhw 说:
2015年7月30日 20:15

因为不会。。而且在老板娘大爷的提醒下我马上就想出了用后缀数组的AC算法


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter