String Algorithms

Suffix Array

SUPER USEFUL Suffix Arrays as a data structure are widely used in areas such as data compression, bioinformatics. They are great for string matching problems.

Let $s$ be a string of length $n$. The $i$-th suffix of $s$ is the substring $s[i\dots n-1]$.

Since it is not efficient to store all the substrings, the suffix array will only store the integers that represent the starting indexes of the all the suffixes of a given string, after the aforementioned suffixes are sorted.

Resources

• https://cp-algorithms.com/string/suffix-array.html

Applications

Finding a substring in a string (ONLINE) → If you know the string $s$ beforehand, you can just use the Z-Algorithm. However, if you don’t know the string $s$ beforehand.