高度数组模板

高度数组是由后缀数组中相邻两个后缀的最长公共前缀的长度组成的数组，可以通过尺取法在(O(n))的时间复杂度内得到

const int maxn=200010;
int lcp[maxn];

void construct_lcp(string S,int *sa,int *lcp){
    int n=S.length();
    for(int i=0;i<=n;i++) rk[sa[i]]=i;
    int h=0;
    lcp[0]=0;
    for(int i=0;i<n;i++){
        int j=sa[rk[i]-1];
        if(h>0) h--;
        for(;j+h<n && i+h<n;h++){
            if(S[j+h]!=S[i+h]) break;
        }
        lcp[rk[i]-1]=h;
    }
}