题意：
给出三个字符串s1,s2,s3；
求一个最长的串满足：
1.它是s1的子串；
2.它是s2的子串；8
3.s3不是它的子串；
s1,s2长度<=50000，，s3长度<=10000
题解：
这道题的前两个条件算是比较裸吧；
求后缀数组，二分答案，在height数组上验证；
如果不会的去看看我之前的题解吧(笑)——链接；
至于第三个条件，这尼玛实在是太容易看错了啊！
如果是“它不是s3的子串”那直接上就好了对吧；
于是我就写了一发样例都不过。。。
至于解决这个，我是用KMP算法，用s3在s1与s2合成的串上匹配；
将所有的匹配点都标记上，然后求一个前缀和，这样就可以O(1)的知道某一段是否存在s3串了；
KMP过程就是找到一个匹配点之后不退出，而是记录匹配点，将j=next[j]后继续匹配；
这样二分验证就可以了，复杂度为O(nlogn+n+nlogn)即为O(nlogn)；
代码：
#include<stdio.h>#include<string.h>#include<algorithm>#define N 120000#define S 200using namespace std;char str[N],dan[N/10];int n,danL,L[4],R[4],vis[4];int next[N],is[N];int hash[N],rank[N],tr[N],sa[N],h[N];inline bool cmp(int x,int y,int len){if(x+len>=n)return 0;return rank[x]==rank[y]&&rank[x+len]==rank[y+len];}void getSA(char* str){register int i;int k,cnt;for(i=0;i<n;i++)hash[str[i]]++;for(i=0,cnt=-1;i<S;i++)if(hash[i])tr[i]=++cnt;for(i=1;i<S;i++)hash[i]+=hash[i-1];for(i=0;i<n;i++)rank[i]=tr[str[i]],sa[–hash[str[i]]]=i;for(k=2;cnt!=n-1;k<<=1){memset(hash,0,sizeof(hash));for(i=0;i<n;i++)hash[rank[i]]++;for(i=1;i<n;i++)hash[i]+=hash[i-1];for(i=n-1;i>=0;i–)if(sa[i]>=(k>>1))tr[sa[i]-(k>>1)]=–hash[rank[sa[i]-(k>>1)]];for(i=1;i<=(k>>1);i++)tr[n-i]=–hash[rank[n-i]];for(i=0;i<n;i++)sa[tr[i]]=i;for(i=1,cnt=0;i<n;i++)tr[sa[i]]=cmp(sa[i-1],sa[i],k>>1)?cnt:++cnt;memcpy(rank,tr,sizeof(tr));}for(i=0;i<=n;i++)if(rank[i])for(k=max(h[rank[i-1]]-1,1);;k++){if(str[sa[rank[i]]+k-1]==str[sa[rank[i]-1]+k-1])h[rank[i]]=k;elsebreak;}}void getnext(char* str,int len){next[0]=-1;int i=0,j=-1;while(i<len)if(j==-1||str[i]==str[j]){i++,j++;next[i]=j;}elsej=next[j];}void kmp(char *str,int n,char *p,int len){getnext(p,len);int i=0,j=0;while(i<n){if(j==-1||str[i]==p[j]){i++,j++;if(j==len)is[i-len]++,j=next[j];}elsej=next[j];}for(i=1;i<n;i++)is[i]+=is[i-1];}inline int where(int x,int len){if(L[1]<=x&&x<=R[1]&&(len<danL||is[x+len-danL]-is[x-1]==0))return 1;if(L[2]<=x&&x<=R[2]&&(len<danL||is[x+len-danL]-is[x-1]==0))return 2;return 0;}bool judge(int mid){int i;memset(vis,0,sizeof(vis));vis[where(sa[0],mid)]++;for(i=0;i<n;i++){if(h[i]>=mid)vis[where(sa[i],mid)]++;else{if(vis[1]&&vis[2])return 1;memset(vis,0,sizeof(vis));vis[where(sa[i],mid)]++;}}if(vis[1]&&vis[2])return 1;return 0;}int main(){//freopen("tt.in","r",stdin);int m,i,j,k,l,r,mid;L[1]=0;scanf("%s",str);n=strlen(str);R[1]=n-1;str[n++]='a'-1;L[2]=n;scanf("%s",str+n);n+=strlen(str+n);R[2]=n-1;scanf("%s",dan);danL=strlen(dan);kmp(str,n,dan,danL);getSA(str);l=0,r=n;while(l<=r){mid=l+r>>1;if(judge(mid))l=mid+1;elser=mid-1;}printf("%d\n",r);return 0;}
追寻爱情，然后发现，爱，从来就是一件千回百转的事。
