Mean:
給你一個字元串，求：至少出現了兩次（無重疊）的子串的種類數。
analyse:
字尾數組中height數組的運用，一般這個數組用得很少。
總體思路：分組統計的思想：将相同字首的字尾分在一個組，然後對于1到len/2的每一個固定長度進行統計ans。
首先我們先求一遍字尾數組，并把height數組求出來。height數組代表的含義是：字典序相鄰(即rank數組相鄰)的兩個字尾的最長公共字首的長度。
由于子串不能重疊，那麼就可以确定出子串長度的取值範圍：1~len/2。(維護sa[]的最大值和最小值是為了判斷排名相鄰兩個字元串的距離是否大于k,隻有大于k才能保證不重疊)。
接下來我們對1~len/2的每一個固定長度進行統計該長度的子串有多少種，一路累加即得答案。
關鍵是要了解使用height數組進行分組統計的過程。
Time complexity: O(nlogn)
Source code:
View Code