The longest common extension problem revisited and applications to approximate string searching

The Longest Common Extension (LCE) problem considers a string s and computes, for each pair (i,j), the longest substring of s that starts at both i and j. It appears as a subproblem in many fundamental string problems and can be solved by linear-time preprocessing of the string that allows (worst-case) constant-time computation for each pair. The two known approaches use powerful algorithms: either constant-time computation of the Lowest Common …