【BZOJ4566】【HAOI2016】找相同字符

后缀自动姬好，好写好调好ac

原题：

给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两

个子串中有一个位置不同。

1 <=n1, n2<= 20000

之前写了个后缀数组+并查集的，因为我只会后缀数组……

后看看dalao们纷纷使用后缀自动姬秒题，决定提高一下自己姿势水平，学一发后缀自动姬

然后根本无法理解啊quq，现在板子差不多理解了，但是自动姬上做DP的延伸还是不能理解quq

多做题应该就能理解了吧……

这题dp具体思路是啥我也没搞懂，直接上结论

每个点的贡献：|right(x)|*(max[x]-max[fa[x]])

具体贡献到答案上，就搞一个b在当前节点上匹配的公共长度l，然后对答案的贡献就是|right(x)|*(l-max[fa[x]])

代码：

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<cmath>

 using namespace std;

 #define ll long long

 int rd(){int z=,mk=;  char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')mk=-;  ch=getchar();}

     while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-'';  ch=getchar();}

     return z*mk;

 }

 char a[],b[];  int n,m;

 int nxt[][],fa[],mx[],sz[];

 int lst=,tt=;

 int cnt[],cntrk[];

 ll f[];

 void ist(int x){

     int p=lst,np=lst=++tt;

     mx[np]=mx[p]+;  sz[np]=;

     while(!nxt[p][x] && p)  nxt[p][x]=np,p=fa[p];

     if(!p)  fa[np]=;

     else{

         int q=nxt[p][x];

         if(mx[p]+==mx[q])  fa[np]=q;

         else{

             int nq=++tt;  mx[nq]=mx[p]+;

             memcpy(nxt[nq],nxt[q],sizeof(nxt[q]));

             fa[nq]=fa[q],fa[q]=fa[np]=nq;

             while(nxt[p][x]==q)  nxt[p][x]=nq,p=fa[p];

         }

     }

 }

 void gtcntrk(){

     for(int i=;i<=tt;++i)  ++cnt[mx[i]];

     for(int i=;i<=n;++i)  cnt[i]+=cnt[i-];

     for(int i=tt;i;--i)  cntrk[cnt[mx[i]]--]=i;

 }

 void gtf(){

     for(int i=tt;i;--i)  sz[fa[cntrk[i]]]+=sz[cntrk[i]];

     for(int i=;i<=tt;++i)

         f[cntrk[i]]=f[fa[cntrk[i]]]+(ll)sz[cntrk[i]]*(mx[cntrk[i]]-mx[fa[cntrk[i]]]);

 }

 int main(){//freopen("ddd.in","r",stdin);

     scanf("%s%s",a+,b+);  n=strlen(a+),m=strlen(b+);

     for(int i=;i<=n;++i)  ist(a[i]-'a');

     gtcntrk(),gtf();

     ll bwl=;  int l=,tmp=,x;

     for(int i=;i<=m;++i){

         x=b[i]-'a';

         if(nxt[tmp][x])  tmp=nxt[tmp][x],++l;

         else{

             while(!nxt[tmp][x] && tmp)  tmp=fa[tmp];

             if(!tmp)  tmp=,l=;

             else  l=mx[tmp]+,tmp=nxt[tmp][x];

         }

         if(tmp!=)  bwl+=f[fa[tmp]]+(ll)sz[tmp]*(l-mx[fa[tmp]]);

     }

     cout<<bwl<<endl;

     return ;

 }

巴特西

【BZOJ4566】【HAOI2016】找相同字符

最新文章

热门文章