bzoj 4566 [Haoi2016]找相同字符SA

4566: [Haoi2016]找相同字符

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 128 Solved: 75
[Submit][Status][Discuss]

Description

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

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

Input

两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母

Output

输出一个整数表示答案

Sample Input

aabb
bbaa

Sample Output

从大到小扫描height数组，合并相邻后缀，因为从大到小枚举，所以当前块中的贡献就是第一个串的后缀数*第二个串的后缀数*当前枚举的height。用并查集维护即可。

算了，学了后缀自动机在来切吧。

 #include<cstring>

 #include<cmath>

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #define ll long long

 #define N 200007

 using namespace std;

 int n,fa[N];

 int cnta[N<<],cntb[N<<],sa[N<<],rk[N<<],a[N<<],b[N<<],tsa[N<<],height[N<<],g[N<<],f[N<<],A[N<<],B[N<<];

 char s1[N],s2[N],s[N*];

 void Get_SA()

 {

     for (int i=;i<=;i++)cnta[i]=;

     for (int i=;i<=n;i++)cnta[(int)s[i]]++;

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

     for (int i=n;i>=;i--)sa[cnta[(int)s[i]]--]=i;

     rk[sa[]]=;

     for (int i=;i<=n;i++)rk[sa[i]]=rk[sa[i-]]+(s[sa[i]]!=s[sa[i-]]);

     for (int i=;rk[sa[n]]!=n;i<<=)

     {

         for (int j=;j<=n;j++)a[j]=rk[j],b[j]=rk[j+i];

         for (int j=;j<=n;j++)cnta[j]=cntb[j]=;

         for (int j=;j<=n;j++)cnta[a[j]]++,cntb[b[j]]++;

         for (int j=;j<=n;j++)cnta[j]+=cnta[j-],cntb[j]+=cntb[j-];

         for (int j=n;j>=;j--)tsa[cntb[b[j]]--]=j;

         for (int j=n;j>=;j--)sa[cnta[a[tsa[j]]]--]=tsa[j];

         rk[sa[]]=;

         for (int j=;j<=n;j++)

             rk[sa[j]]=rk[sa[j-]]+(a[sa[j]]!=a[sa[j-]]||b[sa[j]]!=b[sa[j-]]);

     }

 }

 void Get_Height()

 {

     int len=;

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

     {

         if (len)len--;

         while(s[i+len]==s[sa[rk[i]-]+len])len++;

         height[rk[i]]=len;

     }

 }

 bool cmp(int x,int y){return height[x]>height[y];}

 int find(int x)

 {

     if (f[x]!=x)f[x]=find(f[x]);

     return f[x];

 }

 int main()

 {

     scanf("%s",s1+);int len1=strlen(s1+);

     scanf("%s",s2+);int len2=strlen(s2+);

     n=len1+len2+;

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

         if (i==len1+){s[i]=(char);continue;}

         else s[i]=(i<=len1)?s1[i]-'a'+:s2[i-len1-]-'a'+;

     Get_SA();

     Get_Height();

     /*for (int i=1;i<=n;i++)

         cout<<height[i]<<" ";

     cout<<endl;*/

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

     {

         g[i]=i+;

         f[i]=i;

         if (sa[i]<=len1)A[i]=;

         if (sa[i]>len1+)B[i]=;

     }

     sort(g+,g+n,cmp);

     ll ans=;

     for (int i=;i<=n-;i++)

     {

         int x=find(g[i]),y=find(g[i]-);

         ans+=((ll)A[y]*B[x]+(ll)A[x]*B[y])*height[g[i]];

         A[y]+=A[x],B[y]+=B[x];

         f[x]=y;

     }

     printf("%lld",ans);

 }

巴特西