题意：求两个字符串的最长公共字串（10^5）。枚举字串去匹配是最傻的方法啊。

分析：

很久之前就对后缀数组有所耳闻，是利用基数排序将所有后缀按照字典序排序。

sa[i] 排名第 i 的是后缀 k。

rank[i] 与 sa 互补，rank[i] 后缀 i 排在第几。

height[i] ： sa[i-1] 与 sa[i] 的最长公共前缀长度，即：排 i-1 的后缀 和 排 i 的后缀 的最长公共前缀。

 

代码模板是国家集训的，具体实现不完全清晰。边应用边学习。

 

本题：将这两个字符串用特殊字符连起来，height 的最大值，即答案，但是height 求的任意的两个后缀的最长公共前缀，那么满足条件是，对应的sa 出现的位置在两个字符串中。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;const int maxn = 1000000+ 5;int wa[maxn],wb[maxn],wv[maxn],ww[maxn];int sa[maxn],lcp[maxn],Rank[maxn],rank1[maxn];char str[maxn];inline bool cmp(int *r,int a,int b,int len){     return r[a]==r[b]&&r[a+len]==r[b+len];}void construct_sa(int n,int m){     int i,j,p,*x=wa,*y=wb,*t;     for(i=0;i
          
           =0;i--)         sa[--ww[x[i]]]=i;     for(j=p=1;p
           
            <<=1,m=p){ for(p=0,i=n-j;i
            
             =j) y[p++]=sa[i]-j; } for(i=0;i
             
              =0;i--) sa[--ww[wv[i]]]=y[i]; for(t=x,x=y,y=t,x[sa[0]]=0,p=i=1;i
              
               0) h--; for(;j+h