#
__
Suffix Array
__

##
1. Introduction

**Suffix Array** is a sorted array of all suffixes of a string **T** with usually long length **n**. It is a simple, yet powerful data structure which is used, among others, in full text indices, data compression algorithms, and within the field of bioinformatics. This data structure is very related to __Suffix Tree__ data structure.

##
2. Visualisation

The visualisation of Suffix Array is simply a table where each row represents a suffix and each column represents the attributes of the suffixes.

##
3. Available operations

All available operations on the Sufix Array are listed below.

**Construct Suffix Array (SA)** is the O(**n** log **n**) Suffix Array construction algorithm based on the idea by Karp, Miller, & Rosenberg (1972) that sort prefixes of the suffix in increasing length (1, 2, 4, 8, ...).**Search** utilizes the fact that the suffixes in Suffix Array are sorted and call two binary searches in O(**m** log **n**) to find the first and the last occurrence(s) of pattern string **P** of length **m**.**Longest Common Prefix (LCP)** between two adjacent suffixes (excluding the first suffix) can be computed in O(**n**) using the Permuted LCP (PLCP) theorem.**Longest Repeated Substring (LRS)** is a simple O(**n**) algorithm that finds the suffix with the highest LCP value.**Longest Common Substring (LCS)** is a simple O(**n**) algorithm that finds the suffix with the highest LCP value that comes from two different strings.

##
4. Implementation

You are allowed to use/modify our implementation code for fast Suffix Array+LCP:

__sa_lcp.cpp__

__sa_lcp.java__

__sa_lcp.py__

__sa_lcp.ml__