题解
题目大意：求最小不重复相同子串。
考虑把两个字符串合并起来，求出sa，rk和Height数组。
我们可以从小到大枚举子串长度k，然后再枚举后缀。
具体来说，我们是根据子串字典序从小到大枚举后缀的
如果Height[i]不小于k（即第i-1个子串和第i个子串的最长公共前缀不小于k），
并且如果此后缀的起始点在第一个字符串，cnt1++
否则cnt2++
cnt1和cnt2分别代表最长公共子串出现在第一个字符串和第二个字符串的次数，由于是连续更新的，所以假如上一轮cnt1=1，现在更新cnt2=1那么说明这两个子符串有相同的长度大于k的公共子串，但是不是唯一还不知道。
也就是说这个数字只在两轮更新中有用，如果cnt1>1或cnt2>1都没有价值了（要么没有公共子串，要么有重复的）。
如果要确保唯一性，就要当Height[i]枚举到小于k的时候，如果此时cnt1==1&&cnt2==1的话，则有解。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<bits/stdc++.h> using namespace std; typedef long long ll; string s1,s2,str; int len1,tot,m; const int MAXN=10004; int a[MAXN],Height[MAXN],tax[MAXN],tp[MAXN],sa[MAXN],rk[MAXN]; void RSort(){ for(int i=1;i<=m;i++)tax[i]=0; for(int i=1;i<=tot;i++)tax[rk[i]]++; for(int i=1;i<=m;i++)tax[i]+=tax[i-1]; for(int i=tot;i>=1;i--)sa[tax[rk[tp[i]]]--]=tp[i]; } bool cmp(int *f,int x,int y,int w){ return f[x]==f[y]&&f[x+w]==f[y+w]; } void Suffix(){ m=127; for(int i=1;i<=tot;i++)rk[i]=a[i],tp[i]=i; int p=0;RSort(); for(int w=1;p<tot;w+=w,m=p){ p=0;for(int i=tot-w+1;i<=tot;i++)tp[++p]=i; for(int i=1;i<=tot;i++)if(sa[i]>w)tp[++p]=sa[i]-w; RSort();swap(rk,tp);rk[sa[1]]=p=1; for(int i=2;i<=tot;i++)rk[sa[i]]=cmp(tp,sa[i],sa[i-1],w)?p:++p; } int j=0,k=0; for(int i=1;i<=tot;Height[rk[i++]]=k){ for(k=k?k-1:k,j=sa[rk[i]-1];a[i+k]==a[j+k];k++); } } bool solve(int k,int div){ int cnt1=0,cnt2=0; for(int i=1;i<=tot;i++){ if(Height[i]<k){ if(cnt1==1&&cnt2==1){ return true; } cnt1=0;cnt2=0; if(sa[i]<=div)cnt1++; else if(sa[i]>=div)cnt2++; continue; } if(sa[i]<=div)cnt1++; else if(sa[i]>=div)cnt2++; } return cnt1==1&&cnt2==1;//如果枚举完了也要判断一下 } int main(){ cin>>s1>>s2; len1=s1.length(); str=s1+'#'+s2;//将两个字符串隔开来，避免sa等数组重叠 tot=len1+s2.length()+1; for(int i=1;i<=tot;i++)a[i]=str[i-1]; Suffix();//后缀数组 int ans=-1; for(int i=1;i<=len1;i++){//枚举长度 if(solve(i,len1)){ ans=i;break; } } printf("%d\n",ans); return 0; } |