§2.1, p. 7 — suffixes beginning with a pattern occupy one suffix-array range
ProvedGagieRIndex.Kmers.suffix_rangep2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stringssuffix-array
Let be a terminated text, its suffix array, and any finite pattern. The suffixes beginning with occupy one contiguous suffix-array range:
for some endpoints . If no suffix begins with , the interval is empty.
This range is the basic form in which pattern occurrences are found by suffix-array search and used in the proof of Lemma 8.
Formalization Note The empty range is represented by endpoints with . No restriction on the symbols of is needed.
Preamble
import Mathlib import Definitions.Def_GagieRIndex_Locate_Core
Formal statement
namespace GagieRIndex.Kmers
theorem suffix_range (n σ : ℕ) (T SA : ℕ → ℕ)
(hT : GagieRIndex.Locate.IsText n σ T) (hSA : GagieRIndex.Locate.IsSuffixArray n T SA) (P : List ℕ) :
∃ sp ep, ∀ p, 1 ≤ p → p ≤ n → (P <+: GagieRIndex.Locate.suffix n T (SA p) ↔ sp ≤ p ∧ p ≤ ep) := by sorry
end GagieRIndex.Kmers
Source
Gagie, Navarro, Prezza, Fully-Functional Suffix Trees and Optimal Text Searching in BWT-runs Bounded Space, arXiv:1809.02792v2, p. 7, §2.1, fourth paragraph
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.