LCP 與 height

前言

閱讀此篇前，可先閱讀尾碼數組

LCP

LCP 就是最長公共首碼，在尾碼數組中，\(LCP(i,j)\) 就代表從 \(sa_i\) 開始的尾碼和從 \(sa_j\) 開始的尾碼的最長公共首碼。

height 的定義

\(height[i]=LCP(sa[i],sa[i-1])\)，即從 \(i\) 開始的尾碼與它前一個的尾碼的最長公共首碼。

一些性質

\(height[rak[i]] \ge height[rak[i-1]]-1\)

證明：

當 \(height[rak[i-1]] \le 1\) 時，很好看出，\(height[rak[i]] \ge 0\)，故正確。

當 \(height[rak[i-1]] > 1\) 時,因為 \(LCP(i-1,sa[rak[i-1]-1])=height[rak[i-1]] > 1\)，那麼設這個最長公共為 \(aA\)（其中 \(a\) 代表一個字元 \(A\) 代表一個字元串），從 \(i-1\) 開始的尾碼為 \(aAB\)，從 \(sa[rak[i-1]-1]\) 開始的尾碼為 \(aAC\)，所以從 \(i\) 開始的尾碼為 \(AB\)，從 \(sa[rak[i-1]-1]+1\) 開始的尾碼就為 \(AC\)，所以 \(LCP(i,sa[rak[i-1]-1]+1)=|A|\)。設從 \(sa[rak[i]-1]\) 開始的尾碼就為 \(D\)。

那麼因為 \(aAB > aAC\)，所以 \(AB>AC\)，因為從 \(sa[rak[i]-1]\) 開始的尾碼只比從 \(i\) 開始的尾碼少一位，那麼 \(AB > D \ge AC\)，所以 \(D\) 肯定有一個 \(A\) 的首碼，即 \(height[rak[i]] \ge |A|\)，\(height[rak[i]] \ge height[rak[i-1]]-1\)

Code

void GetHeight(){
	int k=0;
	for(int i=1;i<=n;++i) {
	    if(k) k--;
	    while(s[i+k]==s[sa[rak[i]-1]+k]) ++k;
	    height[rak[i]]=k;
	}
}