Lemma 8, p. 17 — every text substring has a primary occurrence
ProvedGagieRIndex.Kmers.lemma_8burrows-wheeler-transformp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1stringssubstring-complexity
Let be a terminated text with suffix array . Every nonempty substring , where , has an equal-length occurrence that contains a sampled character:
This primary-occurrence property is what lets the distinct-substring count focus on neighborhoods of run-boundary samples.
Formalization Note Equality of the two substrings is expressed pointwise at every offset from through , and . The bounds require a nonempty substring and keep the second occurrence inside .
Preamble
import Mathlib import Definitions.Def_GagieRIndex_Kmers_Smers
Formal statement
namespace GagieRIndex.Kmers
theorem lemma_8 (n σ : ℕ) (T SA : ℕ → ℕ)
(hT : GagieRIndex.Locate.IsText n σ T) (hSA : GagieRIndex.Locate.IsSuffixArray n T SA)
(i j : ℕ) (hi : 1 ≤ i) (hij : i ≤ j) (hj : j ≤ n) :
∃ i', IsPrimary n T SA i' (i' + (j - i)) ∧
∀ t ≤ j - i, T (i' + t) = T (i + t) := 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. 17, Lemma 8; p. 16, Definition 5
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.