Documentation

>>> :set -XOverloadedStrings
>>> sa = buildSuffixArray "abab"
>>> viewSuffixArray "abab" sa
["","ab","abab","b","bab"]
>>> lcp = buildLCPArray "abab" sa
>>> lcp
[0,2,0,1]
>>> viewLCPArray "abab" sa lcp
["","ab","","b"]

>>> :set -XOverloadedStrings
>>> bs = " ab ab a"
>>> n = length $ C.words bs
>>> sa = buildSuffixArray bs
>>> take n . tail $ viewSuffixArray bs sa
[" a"," ab a"," ab ab a"]
>>> lcp = buildLCPArray bs sa
>>> take (n - 1) . tail $ viewLCPArray bs sa lcp
[" a"," ab a"]

O(n)

• lcp[i] = lcp(sa[i], sa[i+1])
• lcp(s[l],s[r]) = minimum[lcp[sa[l]],lcp[sa[l]+1]..lcp[sa[r]-1]]

>>> :set -XOverloadedStrings
>>> bs = "abracadabra"
>>> buildLCPArray bs $ buildSuffixArray bs
[0,1,4,1,1,0,3,0,0,0,2]

O(n)

>>> :set -XOverloadedStrings
>>> naiveLCP "abc0" "abc1"
3
>>> naiveLCP "ab" "a"
1
>>> naiveLCP "" ""
0