The prefix-substring matching problem Gu, Farach, and Beigel, SODA 1994 consists in preprocessing a string s of length n for the following queries: given a triple (i, j, k) ∈ 0, …, |s|³ with 1 ≤ j ≤ k, representing a prefix s1: i and a substring sj: k of s, find the longest prefix of s that is a suffix of s1: isj: k. This is an useful primitive in e. g. dynamic text indexing, compressed pattern matching, and pattern matching on block graphs. The border tree uses some basic periodicity properties to answer such queries in 𝒪 (log n) time after 𝒪 (n) time preprocessing of s. We design a linear-space structure that answers such queries in constant time after 𝒪 (n) time preprocessing of s over a polynomial alphabet, which is worst-case optimal.
Gawrychowski et al. (Thu,) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: