úÎ8Ü7A     Joshua Simmons 2017BSD3joshua.simmons@emptypath.comunstableSafe cA character in a string (or set of strings) we're going to compute the suffix array of. Includes  markers for the end of strings.'Used to mark the end of a string. The b parameter is used to encode which string this is the end of, in cases where there are multiple."An actual character in the string.FYields the non-empty suffixes of a list in order of decreasing length.This differs from 8 in that it does not include the empty list at the end.Convenience value containing  s in order.^Prepare a list of strings to compute the suffix array of them. Just wraps every character in  and adds ;s to the end of each string, and concatenates it together.Convenience function to  a single string.ÿDA naively implemented suffix array implementation which will be used for correctness checking and possibly to benchmark against. Shouldn't usually be used in production code, as it is quite slow in the worst case. In cases with few identical suffixes, it can actually perform quite well. See benchmarks for some details._worst case O(n^2 lg n) time (where n is the sum of the string lengths + the number of strings)Convenience wrapper around  for a single string.Bworst case O(n^2 lg n) time (where n is the length of the string)]A naively implemented LCP implementation, used for correctness testing the actual algorithm.’The Longest Common Prefix list gives the longest common prefix of each suffix and the previous suffix, with the suffixes in lexicographic order._worst case O(n^2 lg n) time (where n is the sum of the string lengths + the number of strings)jThe LCP part is an extra O(n^2) in addition to the work of computing the suffix array in the first place. Convenience wrapper around  for a single string.Bworst case O(n^2 lg n) time (where n is the length of the string)jThe LCP part is an extra O(n^2) in addition to the work of computing the suffix array in the first place. >Take a sorted list of elements and replace each value with an z such that any comparisons between elements in the original list would yield exactly the same result in the output list.0i.e.: let rs = rank xs in all [ (xs!!i)  (xs!!j) == (rs!!i) ] (rs!!j) | let idx = [0 .. length xs - 1], i <- idx, j <- idx ]       Joshua Simmons 2017BSD3joshua.simmons@emptypath.comNone:OT $Holds the computed suffix array data5The actual array of suffixes in lexicographic order.The original string(s) with $ values included after each string.RLongest Common Prefix of each suffix with the previous one in lexicographic orderLCompute the suffix array of the given string(s) concatenated together with  s after each.]worst case O(n lg n) time (where n is the sum of the string lengths + the number of strings)TConvenience function to compute the suffix array of a single string. (Still gets a  at the end)@worst case O(n lg n) time (where n is the length of the string)QConvenience function to just give a list of the suffixes in lexicographic order.ZConvenience function to just give a list characters in the concatenated original strings.ˆConvenience function to just give a list of the longest common prefix of every suffix with the previous suffix in lexicographic order.         !"#$%+suffix-array-0.3.0.0-45BorTZT4KqJOOE9cIHt1XData.SuffixArray.InternalData.SuffixArray Data.ListtailsAlphaSentinalsuffixesprepare prepareOnenaivenaiveOnenaiveLcp naiveLcpOnerank $fEqAlpha $fOrdAlpha $fShowAlpha SuffixArray toSuffixestoAlphastoLcp suffixArraysuffixArrayOne justSuffixes justAlphasjustLcp$fEqSuffixArray$fOrdSuffixArray$fShowSuffixArrayghc-prim GHC.TypesInt sentinals GHC.ClassescompareArr