本文共 1557 字，大约阅读时间需要 5 分钟。
题目链接：
两个字符串的最长公共字串。
求出height数组后直接二分答案就可以了，或者线性扫描一遍。
1 //STATUS:C++_AC_594MS_4800KB 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 #define LL __int64 15 #define pii pair 16 #define mem(a,b) memset(a,b,sizeof(a)) 17 #define lson l,mid,rt<<1 18 #define rson mid+1,r,rt<<1|1 19 #define PI acos(-1.0) 20 const int N=200010,INF=0x3f3f3f3f,MOD=10000,STA=8000010; 21 //const LL LNF=0x3f3f3f3f3f3f3f3f; 22 const double DNF=1e13; 23 // 24 inline int Max(int a,int b){ return a>b?a:b;} 25 inline int Min(int a,int b){ return a =0;i--)sa[--c[x[i]]]=i; 43 for(k=1;k<=n;k<<=1){ 44 p=0; 45 //直接利用sa数组排序第二关键字 46 for(i=n-k;i =k)y[p++]=sa[i]-k; 48 //基数排序第一关键字 49 for(i=0;i =0;i--)sa[--c[x[y[i]]]]=y[i]; 53 //根据sa和x数组计算新的x数组 54 swap(x,y); 55 p=1;x[sa[0]]=0; 56 for(i=1;i =n)break; //已经排好序，直接退出 59 m=p; //下次基数排序的最大值 60 } 61 } 62 63 void getHeight(int s[],int n) 64 { 65 int i,j,k=0; 66 for(i=0;i<=n;i++)rank[sa[i]]=i; 67 for(i=0;i >1; 80 ok1=ok2=0; 81 if(sa[1] len1)ok2=1; 83 for(i=2;i<=n;i++){ 84 if(height[i] len1)ok2=1; 87 if(ok1 && ok2)break; 88 } 89 if(ok1 && ok2)ret=mid,l=mid+1; 90 else r=mid-1; 91 } 92 return ret; 93 } 94 95 int main() 96 { 97 // freopen("in.txt","r",stdin); 98 int i,j; 99 while(~scanf("%s",s) && s[0]!='#')100 {101 len1=strlen(s);102 for(i=0;i
转载于:https://www.cnblogs.com/zhsl/archive/2013/04/24/3040835.html