LCP Array

 1func newLongestCommonPrefixArray(s string, sa []int) []int {
 2	n := len(s)
 3	lcp := make([]int, n-1)
 4	ra := make([]int, n)
 5	for i := 0; i < n; i++ {
 6		ra[sa[i]] = i
 7	}
 8
 9	for i, h := 0, 0; i < n; i++ {
10		if ra[i] == 0 {
11			continue
12		}
13		if h > 0 {
14			h--
15		}
16		for j := sa[ra[i]-1]; j+h < n && i+h < n; h++ {
17			if s[j+h] != s[i+h] {
18				break
19			}
20		}
21		lcp[ra[i]-1] = h
22	}
23
24	return lcp
25}
26