A Failure Function for Multiple Two-dimensional Pattern Matching
Maxime Crochemore, Costas S. Iliopoulos, Maureen Korda, James F. Reid · 2000
1 Introduction Given a string x of length n and a pattern p of length m, the string prefixmatching problem is that of computing the longest prefix of p which occurs at each position of x. Main and Lorentz introduced the notion of string prefixmatching in [15] and presented a linear time algorithm for it; their algorithm was an adaptation of the Knuth, Morris and Pratt algorithm [12].