Generalized suffix array

In computer science, a generalized suffix array is a suffix array containing all suffixes for a set of strings. Given the set of strings $S=S_{1},S_{2},S_{3},...,S_{k}$ of total length $n$, it is a lexicographically sorted array of all suffixes of each string in $S$.

Definition

The algorithm for constructing the generalized suffix array is as follows:

• Let $S=[S_{1},S_{2},...,S_{k}]$ be the set of strings for which to construct the suffix array for.
• Let $N$ denote the sum of the lengths of all strings in $S$ and $n$ the length of the longest string in $S$.
• A straightforward sorting approach would concatenate all strings in S and utilize Manber & Myers (1990) algorithm to sort the concatenated string.
• Let $A_{(}i,j)$ represent the suffix of $S$ that starts at position $j$ of the $i$-string $S^{i}$ ∈ $S$. $(i,j)$ is the initial position of suffix $S_{(}i,j)$.
• Let $P$ indicate the sorted array of suffixes of the strings in the set $S$. So, $P[k]$ indicates the starting position of the $k-th$ smallest suffix of the set of strings. The array P satisfies $S_{P}[0]\leq S_{P}[1]\leq ..\leq S_{P}[N-1]$, where $\leq$ denotes lexicographical order.

This approach would cost $O(NlogN)$ time.

Application

A generalized suffix array can be used to compete the longest common subsequence of the strings in the set in linear time, whereas a naïve implementation would compute this information in quadratic time.

References

• Manber, Udi; Myers, Gene (1990). Suffix arrays: a new method for on-line string searches. First Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 319–327.
• Shi, Fei (1996). "Suffix arrays for multiple strings: A method for on-line multiple string searches". Lecture Notes in Computer Science. 1179. Springer Berlin Heidelberg. doi:10.1007/BFb0027775. ISBN 978-3-540-62031-0.