题目链接：Codeforces Round #244 (Div. 2) D. Match & Catch
题意：
给你两个串A,B，问你是否存在一个串x，使得x是A,B的子串，并且只在A,B中出现一次。
题解：
对于两个串分别建立后缀自动机，更新一下right集，然后dfs一下，更新一下答案就行了。
1 #include<bits/stdc++.h> 2 #define mst(a,b) memset(a,b,sizeof(a)) 3 #define F(i,a,b) for(int i=(a);i<=(b);++i) 4 using namespace std; 5 6 const int N=5e3+7,tyn=26,M=N*2; 7 struct SAM{ 8 int tr[M][tyn],f[M],ml[M],ed,last,p,x,r,q; 9 int cnt[M],b[M],d[M]; 10 inline int gid(char x){return x-'a';} 11 inline void nc(int s,int &p){ 12 ml[p=++ed]=s,f[ed]=cnt[ed]=0,mst(tr[ed],0); 13 } 14 void clear(){ed=0,nc(0,last);} 15 void add(int w){ 16 nc(ml[x=last]+1,p),last=p,cnt[p]=1; 17 while(x&&!tr[x][w])tr[x][w]=p,x=f[x]; 18 if(!x)f[p]=1; 19 else if(ml[x]+1==ml[q=tr[x][w]])f[p]=q; 20 else{ 21 nc(ml[x]+1,r),f[r]=f[q],f[p]=f[q]=r; 22 memcpy(tr[r],tr[q],sizeof(tr[r])); 23 while(x&&tr[x][w]==q)tr[x][w]=r,x=f[x]; 24 } 25 } 26 void upright(int mx=0){ 27 F(i,0,ed)d[i]=0; 28 F(i,1,ed)d[mx<ml[i]?mx=ml[i]:ml[i]]++; 29 F(i,1,mx)d[i]+=d[i-1]; 30 F(i,1,ed)b[d[ml[i]]--]=i; 31 for(int i=ed;i;--i)cnt[f[b[i]]]+=cnt[b[i]]; 32 }//从1开始 33 void build(char *s){for(int i=1;s[i];i++)add(gid(s[i]));} 34 }sam[2]; 35 36 char s[N]; 37 int ans=INT_MAX; 38 39 void go(int x,int y,int len) 40 { 41 if(len>ans)return; 42 if(len&&sam[0].cnt[x]==1&&sam[1].cnt[y]==1) 43 { 44 ans=min(ans,len); 45 return; 46 } 47 F(i,0,25)if(sam[0].tr[x][i]&&sam[1].tr[y][i]) 48 go(sam[0].tr[x][i],sam[1].tr[y][i],len+1); 49 } 50 51 int main(){ 52 scanf("%s",s+1); 53 sam[0].clear(),sam[0].build(s),sam[0].upright(); 54 scanf("%s",s+1); 55 sam[1].clear(),sam[1].build(s),sam[1].upright(); 56 go(1,1,0); 57 printf("%d ",ans==INT_MAX?-1:ans); 58 return 0; 59 }