首页 > 代码库 > Bzoj4566 [Haoi2016]找相同字符
Bzoj4566 [Haoi2016]找相同字符
Submit: 413 Solved: 224
Description
给定两个字符串，求出在两个字符串中各取出一个子串使得这两个子串相同的方案数。两个方案不同当且仅当这两
个子串中有一个位置不同。
Input
两行，两个字符串s1，s2，长度分别为n1，n2。1 <=n1, n2<= 200000，字符串中只有小写字母
Output
输出一个整数表示答案
Sample Input
aabb
bbaa
bbaa
Sample Output
10
HINT
Source
字符串 后缀数组
后缀自动机解法：http://www.cnblogs.com/SilverNebula/p/6562205.html
别人：听说这题可以用后缀自动机秒，但是我不会后缀自动机只好用后缀数组写了好麻烦呀
我：我知道这题可以用后缀自动机秒，但是我死活学不会后缀数组啊
（黑人问号.jpg）
研究了一上午后缀数组，试着写了一发，最后靠着标准代码比对可算是A了
把两个串拼在一起，中间用个大编码字符隔开，结尾加个0编码字符，建立后缀数组。
一个暴力的算法是在rank数组中枚举起点，然后往后一直扫到串尾，过程中维护最小height，如果扫到一个串和起点不在同一个串中，答案+=当前height
发现答案主要和height有关，于是把后缀串按height从大到小排序，依次添加进一个集合，依据先前添加进集合的两个串的子串数量（先添加进的height更大，所以当前对之前的有贡献），用乘法原理算答案。
参考了这里：http://blog.csdn.net/fzhvampire/article/details/51674402
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 using namespace std; 9 const int mxn=400105; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14 return x*f; 15 } 16 int sa[mxn],rk[mxn],ht[mxn],r[mxn]; 17 int cnt[mxn],wa[mxn],wb[mxn],wv[mxn]; 18 inline int cmp(int *r,int a,int b,int l){ 19 return r[a]==r[b] && r[a+l]==r[b+l]; 20 } 21 void GetSA(int *sa,int *rk,int n,int m){ 22 int i,j,p; 23 int *x=wa,*y=wb; 24 for(i=0;i<m;i++)cnt[i]=0; 25 for(i=0;i<n;i++)cnt[x[i]=r[i]]++; 26 for(i=1;i<m;i++)cnt[i]+=cnt[i-1]; 27 for(i=n-1;i>=0;i--)sa[--cnt[x[i]]]=i; 28 for(j=1,p=1;p<n;j<<=1,m=p){ 29 for(p=0,i=n-j;i<n;i++)y[p++]=i; 30 for(i=0;i<n;i++) 31 if(sa[i]>=j)y[p++]=sa[i]-j; 32 for(i=0;i<n;i++)wv[i]=x[y[i]]; 33 for(i=0;i<m;i++)cnt[i]=0; 34 for(i=0;i<n;i++)cnt[wv[i]]++; 35 for(i=1;i<m;i++)cnt[i]+=cnt[i-1]; 36 for(i=n-1;i>=0;i--)sa[--cnt[wv[i]]]=y[i]; 37 swap(x,y); 38 p=1;x[sa[0]]=0; 39 for(i=1;i<n;i++){ 40 x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; 41 } 42 } 43 } 44 void GetHeight(int n){ 45 int i,j,k=0; 46 for(i=1;i<=n;i++)rk[sa[i]]=i; 47 for(i=0;i<n;i++){ 48 if(k)k--; 49 j=sa[rk[i]-1]; 50 while(r[i+k]==r[j+k])k++; 51 ht[rk[i]]=k; 52 } 53 return; 54 } 55 int CMP(int a,int b){return ht[a]>ht[b];}//按height排序 56 int fa[mxn],id[mxn]; 57 int st[mxn],ed[mxn],lim; 58 int find(int x){ 59 return fa[x]==x?x:fa[x]=find(fa[x]); 60 } 61 long long ans=0; 62 void solve(int n){ 63 int i,j; 64 for(i=0;i<n;i++)id[i]=i,fa[i]=i; 65 sort(id+1,id+n+1,CMP); 66 for(i=0;i<n;i++){ 67 if(sa[i]<lim)st[i]=1;// 68 ed[i]=1-st[i]; 69 } 70 for(i=0;i<n;i++){ 71 int now=id[i]; 72 // printf("now:%d\n",id[i]); 73 if(!now)continue; 74 int x=find(now),y=find(now-1); 75 ans+=(long long)(st[x]*ed[y]+st[y]*ed[x])*(long long)ht[now]; 76 st[x]+=st[y]; 77 ed[x]+=ed[y]; 78 fa[y]=x; 79 } 80 printf("%lld\n",ans); 81 return; 82 } 83 char s[mxn]; 84 int main(){ 85 int i,j; 86 scanf("%s",s); 87 int len=strlen(s); 88 for(i=0;i<len;i++)r[i]=s[i]-‘a‘+1; 89 r[len]=27;lim=len; 90 scanf("%s",s); 91 int l2=strlen(s); 92 for(i=len+1;i<=l2+len;i++)r[i]=s[i-len-1]-‘a‘+1; 93 len+=l2; 94 r[++len]=0; 95 //read 96 GetSA(sa,rk,len+1,29); 97 GetHeight(len); 98 solve(len); 99 /* printf("SA: ");100 for(i=1;i<=n;i++)printf("%d ",sa[i]);101 printf("\nrk: ");102 for(i=0;i<n;i++)printf("%d ",rk[i]);103 printf("\nht: ");104 for(i=0;i<n;i++)printf("%d ",ht[i]);105 printf("\nfin\n");*/106 return 0;107 }108 /*109 aaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa110 asbbbbbbcccccccccaaaaaaaaaaaaaaaa111 7139112 */
Bzoj4566 [Haoi2016]找相同字符
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。