[ Suffix Array Longest Common Prefix (LCP) ] 後綴數組之最長共同前綴(高度數組)

不解釋了，可以在$\ord N$時間內得到，N是字串長度
以下提供模板:

	/*
	h:高度數組
	sa:後綴數組
	rank:排名
	*/
	inline void suffix_array_lcp(const char *s,int len,int *h,int *sa,int *rank){
	for(int i=0;i<len;++i)rank[sa[i]]=i;
	for(int i=0,k=0;i<len;++i){
	if(rank[i]==0)continue;
	if(k)--k;
	while(s[i+k]==s[sa[rank[i]-1]+k])++k;
	h[rank[i]]=k;
	}
	h[0]=0;
	}

view raw LCP.cpp hosted with ❤ by GitHub