后缀三兄弟&回文双子星
orz hhw
posted @ 2015年7月20日 17:03
in 算法学习
with tags
字符串 模板 后缀数组 后缀自动机 算法学习 bzoj Manacher 回文自动机
, 5483 阅读
字符串这一块一直都不太懂，处理前缀的还好，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);
}
2015年7月28日 11:17
字符串小能手
2015年7月29日 11:04
尛字符串大爷
2015年7月29日 13:53
尛当场A T2的后缀数组大爷
2015年7月30日 17:04
为什么不使用神器后缀树呢？
2015年7月30日 20:15
因为不会。。而且在老板娘大爷的提醒下我马上就想出了用后缀数组的AC算法