Longest common factor of two words

Maxime Crochemore (1)

1 LIGM - Laboratoire d'Informatique Gaspard-Monge

The LCF of two words u and v is the maximal length of a common factor of u and v. A linear time algorithm to compute LCF is given, based on a linear time algorithm to build the minimal suffix automaton of a word. The algorithm naturally turns into a real-time string-matching algorithm.

Domaines: Algorithme et structure de données [cs.DS]

Maxime Crochemore. Longest common factor of two words. TAPSOFT'87 (Pisa, 1987), 1987, Pise, Italy. pp.26-36, ⟨10.1007/3-540-17660-8_45⟩. ⟨hal-00620786⟩