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 abc and bcd, then the suffix of the two strings will be {abc, bc, c} and {bcd, cd, d} respectively. If we sort them according to alphabetical order, it will be rearranged as below, Figure 1. Sorted Suffices of Both abc and bcd It is not difficult to tell that the LCS is bc,
Read full article from Suffix Array Part 3 — Longest Common Substring (LCS) | roman10
