原理

定义rank[i]表示suffix[i]在所有后缀中的字典序排名；sa[i]表示字典序排名为i的后缀是suffix[sa[i]]

定义height[i]表示排名为i的后缀和排名为i-1的后缀的LCP(最长公共前缀)

可以证明，$height[rank[i]]>=height[rank[i-1]]-1$

然后有对于两个后缀x,y，$LCP(x,y)=min_{i \in (rank[x],rank[y]]}{height[i]}$

所以预处理一个ST表就可以O(1)查LCP了

做法

可以用倍增+基数排序来求

具体怎么做还是背板子吧2333

1 inline void build(){ 2     for(int i=1;i<=N;i++) cnt[s[i]]=1; 3     for(int i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 4     for(int i=N;i;i--) rnk[i]=cnt[s[i]]; 5     for(int j=-1,l=1;j!=N;l<<=1){ 6         CLR(cnt,0); 7         for(int i=1;i<=N;i++) cnt[rnk[i+l]]++; 8         for(int i=1;i<=M;i++) cnt[i]+=cnt[i-1]; 9         for(int i=N;i;i--) tmp[cnt[rnk[i+l]]--]=i;10         CLR(cnt,0);11         for(int i=1;i<=N;i++) cnt[rnk[i]]++;12         for(int i=1;i<=M;i++) cnt[i]+=cnt[i-1];13         for(int i=N;i;i--) sa[cnt[rnk[tmp[i]]]--]=tmp[i];14         memcpy(tmp,rnk,sizeof(tmp));15         rnk[sa[1]]=j=1;16         for(int i=2;i<=N;i++){17             if(tmp[sa[i]]!=tmp[sa[i-1]]||tmp[sa[i]+l]!=tmp[sa[i-1]+l]) j++;18             rnk[sa[i]]=j;19         }M=j;20     }21     22     for(int i=1,j=0;i<=N;i++){23         if(rnk[i]==1) continue;24         if(j) j--;25         int x=sa[rnk[i]-1];26         while(x+j<=N&&i+j<=N&&s[x+j]==s[i+j]) j++;27         hei[rnk[i]]=j;28     }29 }

注意rank和tmp开两倍空间