Tight comparison bounds for the string prefix-matching problem (Q685487)

The authors study the following generalization of the standard string matching problem, called string prefix-matching problem. Given a text string T\([1\dots n]\) and a pattern string P\([1\dots n]\), compute an integer array \(\pi [1\dots n]\) such that for each \(i\) \((1 \leq i \leq n)\), \(\pi [i] \leq m\) and \(\pi [i]\) is the largest integer satisfying T\([i..i + \pi [i] - 1]=\text{P}[1..\pi [i]]\). I. e., \(\pi[i]\) gives the longest prefix of the pattern P that coincides with a substring of the text T starting in position \(i\). In this paper the authors give upper and lower bounds for the exact complexity of the string prefix-matching in the deterministic sequential comparison model.