思路
后缀数组的水题
把两个字符串拼起来, 找到最大的 height 满足 sa[i-1] 和 sa[i] 不在同一子串中即可
代码
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- using namespace std;
- const int MAXN = 100100*2;
- struct Node{
- int pos,r[2];
- }x[MAXN],midx[MAXN];
- int barrel[MAXN],ranks[MAXN],sa[MAXN],height[MAXN],n,lena,lenb;
- char s[MAXN],t[MAXN];
- int c_sort(int n,int lim){
- for(int i=0;i<2;i++){
- memset(barrel,0,sizeof(barrel));
- for(int j=1;j<=n;j++)
- barrel[x[j].r[i]]++;
- for(int j=1;j<=lim;j++)
- barrel[j]+=barrel[j-1];
- for(int j=n;j>=1;j--)
- midx[barrel[x[j].r[i]]--]=x[j];
- for(int j=1;j<=n;j++)
- x[j]=midx[j];
- }
- int cnt=1;
- ranks[x[1].pos]=1;
- for(int i=2;i<=n;i++)
- if(x[i].r[0]==x[i-1].r[0]&&x[i].r[1]==x[i-1].r[1])
- ranks[x[i].pos]=cnt;
- else
- ranks[x[i].pos]=++cnt;
- return cnt;
- }
- void cal_sa(int n){
- for(int i=1;i<=n;i++)
- x[i]=(Node){i,s[i],0};
- int cnt=c_sort(n,2000);
- for(int i=1;cnt<n;i<<=1){
- for(int j=1;j<=n;j++)
- x[j]=(Node){j,(i+j<=n)?ranks[i+j]:0,ranks[j]};
- cnt=c_sort(n,cnt);
- }
- for(int j=1;j<=n;j++)
- sa[ranks[j]]=j;
- for(int i=1,j=0,k;i<=n;height[ranks[i++]]=j)
- for(j?j--:0,k=sa[ranks[i]-1];s[i+j]==s[j+k];j++);
- }
- int main(){
- scanf("%s",t+1);
- lena=strlen(t+1);
- for(int i=1;i<=lena;i++)
- s[i]=t[i];
- n+=lena;
- s[++n]='#';
- scanf("%s",t+1);
- lenb=strlen(t+1);
- for(int i=1;i<=lenb;i++)
- s[n+i]=t[i];
- n+=lenb;
- cal_sa(n);
- int ans=0;
- for(int i=2;i<=n;i++){
- if((sa[i-1]<=lena&&sa[i]>lena+1)||(sa[i-1]>lena+1&&sa[i]<=lena))
- ans=max(ans,height[i]);
- }
- printf("%d\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2977325.html