還記得SA數組嘛？

之前在似曾相識的那一提，有很認真的討論過關於SA數組的construction和他的概念等，並在最後面的地方，隱約提到了有關 h 數組的事情，也提到了幾個定理，但並沒有好好的講清楚，在這裡要將他們一一證明。

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝要進入主題了～

Longest Common Prefix:（照字面上就是最長的共同前綴，而他確實是這樣的東西）
    
名詞解釋：
i =x j: 兩個後綴前x個字元相同 
sa[i]: 第i名後綴是第幾個後綴
ra[i]: 第i個後綴是第幾名後綴
lcp( i, j ): 第i個後綴與第j個後綴的最長公共前綴
LCP( i, j ): 第i名後綴與第j名後綴的最長公共前綴（照字典序sort後）
h[i]: LCP( rank[i]-1, rank[i] )

------------------------------------------------------------------------------------- 


一。 LCP Lemma:  LCP( i, j ) = min( LCP( i, k ), LCP( k,  j ) ); { i<=k<=j }


proof: 


1. 設 x = min( LCP(i,k), LCP(k,j) ), 則i =x k 且 k =x j, 故LCP(i,j) >= x


2. 設LCP(i,j) > x, 則 i[x+1] = j[x+1].
    因 i < k < j 且 i =x j =x k, 故 i[x+1]<=k[x+1]<=j[x+1].
    因此i[x+1] = k[x+1] = j[x+1], 矛盾!!!!


3. 由1.和2.可知LCP(i,j) = x = min( LCP(i,k), LCP(k,j) ).


-------------------------------------------------------------------------------------


二。 LCP Theorem: LCP( i, j ) = min( LCP( k, k-1 ) ) { k = i+1~j }

proof:


1. j-i == 0 和 j-i == 1 皆成立


2. 若 j-i == m 成立，則LCP( i, j ) = min( LCP( k-1, k ) ) { k = i+1~j }，
    由LCP Lemma -> LCP( i-1, j ) = min( LCP(i-1, i ), LCP( i, j ) )
    -> LCP( i-1, j ) = min( LCP( k-1, k ) ) { k = i~j } -> j-i == m+1成立


-------------------------------------------------------------------------------------


三。LCP Corollary: LCP( i, k ) <= LCP( j, k ) { i <= j <= k }

proof: LCP( i, k ) = min( LCP( i, j ), LCP( j, k ) ) <= LCP( j, k )

-------------------------------------------------------------------------------------

四。h[]數組的特性：h[i] >= h[i-1] - 1

proof: