Suffix array can be used to find longest common substring (LCS) among multiple strings. This post illustrate the algorithm by an example of finding LCS among two strings.

Algorithm

The idea is that LCS for two strings is the longest common prefix of some suffices of the two string. Suppose we have two strings [...]

This is part 2 of the post “suffix array”, which covers the string matching/searching problem that can be solved by suffix array. You may want to read part 1 first.

String Matching/Searching

Once we have the suffix array, it’s easy to check if another string appears in the input string/text or not. If [...]

Suffix Array

Suffix array is an array which contains the suffix of a string sorted in lexicographical (alphabetical) order. It’s used in several string matching/searching problems. This post briefly explains suffix array, its applications and provides C implementations to some of them.

To compute the suffix array, we first find all the suffix. In [...]

I’ve learned Knuth-Morris-Pratt Algorithm (KMP) several times. Several weeks after I learned it, if I am asked to solve the string/pattern matching problem, I only know there’s a KMP algorithm that does it efficiently at the time complexity of O(n+m). How to do it? I need to read it again. So I know I’ll need [...]

A More General Problem

The pre-computation of KMP finds the longest suffix of a sub-pattern P[0..j] (where j is [0, m-1], m is the length of the pattern) that is also the prefix of this sub-pattern.

A more general problem is to find the longest suffix of a pattern X[0..lx-1], which is also the [...]