import Mathlib /-! # Find The Index Of The First Occurrence In A String Given two strings needle and haystack, return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack. ## Constraints - 1 <= haystack.length, needle.length <= 10^4 - haystack and needle consist of only lowercase English characters. ## Provided examples - `haystack = "sadbutsad", needle = "sad"` → `0` - `haystack = "leetcode", needle = "leeto"` → `-1` - `haystack = "a", needle = "a"` → `0` ## Synthesized negative examples - invalid input: `haystack = "A", needle = "a"` ([structural] a predicate that admits haystack and needle consist of only lowercase English characters.. uppercase in haystack; catches predicate that accepts any letter) - invalid input: `haystack = "a", needle = "A"` ([structural] a predicate that admits haystack and needle consist of only lowercase English characters.. uppercase in needle; same shape as the first) - invalid input: `haystack = "a b", needle = "a"` ([structural] a predicate that admits haystack and needle consist of only lowercase English characters.. space in haystack; defeats predicate using .islower()) - `haystack = "sadbutsad", needle = "sad"` → `1` is wrong ([structural] specification does not specify 0-based indexing; 1-based gives one off. first occurrence at 0-based index 0, but 1-based index 1) - `haystack = "leetcode", needle = "leeto"` → `0` is wrong ([structural] occurrence is interpreted as a subsequence rather than contiguous substring. leeto is a subsequence of leetcode, so not absent under this reading) - `haystack = "a", needle = "a"` → `1` is wrong ([structural] returned index is not specified as zero-based. first occurrence at position 0 but returns 1) -/ namespace PFindTheIndexOfTheFirstOccurrenceInAString abbrev Input := (String) × (String) abbrev Output := Int /-! ### Specification helpers -/ /-- `needle` occurs contiguously in `haystack` starting at zero-based index `i`. -/ def OccursAt (needle haystack : String) (i : Nat) : Prop := i + needle.length ≤ haystack.length ∧ needle.toList.IsPrefix (haystack.toList.drop i) /-! ### Validity predicate (V) -/ /-- Valid input: needle and haystack are nonempty strings of at most 10^4 lowercase English letters. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.1.length && input.1.length ≤ 10^4 && 1 ≤ input.2.length && input.2.length ≤ 10^4 && input.1.toList.all (fun c => 'a' ≤ c && c ≤ 'z') && input.2.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is `-1` when `needle` occurs nowhere in `haystack`, else the least zero-based index of an occurrence. -/ def firstOccurrence_spec (input : Input) (result : Output) : Prop := (result = -1 ∧ ∀ i : Nat, ¬ OccursAt input.1 input.2 i) ∨ IsLeast {r : Int | ∃ i : Nat, OccursAt input.1 input.2 i ∧ r = (i : Int)} result /-! ### Decidable specification (P_check) -/ /-- Decides whether `needle` occurs in `haystack` at the fixed index `i`: a decidable Nat inequality together with a decidable list-prefix test. -/ instance decidableOccursAt (needle haystack : String) (i : Nat) : Decidable (OccursAt needle haystack i) := inferInstanceAs (Decidable (i + needle.length ≤ haystack.length ∧ needle.toList.IsPrefix (haystack.toList.drop i))) /-- Decides the full specification. Every occurrence index `i` satisfies `i + needle.length ≤ haystack.length`, hence `i < haystack.length + 1`, so both unbounded quantifiers reduce to bounded ones over `Nat`, which Lean decides through `Nat.decidableBallLT` and `Nat.decidableExistsLT`. -/ instance decidableFirstOccurrenceSpec (input : Input) (result : Output) : Decidable ((result = -1 ∧ ∀ i : Nat, ¬ OccursAt input.1 input.2 i) ∨ IsLeast {r : Int | ∃ i : Nat, OccursAt input.1 input.2 i ∧ r = (i : Int)} result) := decidable_of_iff ((result = -1 ∧ ∀ i < input.2.length + 1, ¬ OccursAt input.1 input.2 i) ∨ ((∃ i < input.2.length + 1, OccursAt input.1 input.2 i ∧ result = (i : Int)) ∧ ∀ i < input.2.length + 1, OccursAt input.1 input.2 i → result ≤ (i : Int))) (by constructor · -- Bounded form → specification. intro hb cases hb with | inl hnone => apply Or.inl refine ⟨hnone.1, fun i hocc => ?_⟩ have h1 : i + input.1.length ≤ input.2.length := hocc.1 exact hnone.2 i (by omega) hocc | inr hleast => apply Or.inr constructor · rcases hleast.1 with ⟨i, _, hocc, hresult⟩ exact ⟨i, hocc, hresult⟩ · intro y hy rcases hy with ⟨i, hocc, hresult⟩ rw [hresult] have h1 : i + input.1.length ≤ input.2.length := hocc.1 have hi : i < input.2.length + 1 := by omega exact hleast.2 i hi hocc · -- Specification → bounded form. intro hs cases hs with | inl hnone => exact Or.inl ⟨hnone.1, fun i _ => hnone.2 i⟩ | inr hleast => obtain ⟨hmem, hmin⟩ := hleast rcases hmem with ⟨i, hocc, hresult⟩ have h1 : i + input.1.length ≤ input.2.length := hocc.1 have hi : i < input.2.length + 1 := by omega refine Or.inr ⟨⟨i, hi, hocc, hresult⟩, fun j _ hoccj => ?_⟩ -- `lowerBounds` binds its element strictly implicitly, -- so `hmin` is applied to the membership proof alone. exact hmin ⟨j, hoccj, rfl⟩) /-- Executable checker obtained mechanically from the specification. -/ def firstOccurrence_check (input : Input) (result : Output) : Bool := @decide (firstOccurrence_spec input result) (by unfold firstOccurrence_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem firstOccurrence_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : firstOccurrence_check input result ↔ firstOccurrence_spec input result := by simp [firstOccurrence_check] /-! ### Implementation helpers -/ /-- Length of the longest prefix of `needle` that is a suffix of the matched prefix extended by `c`. -/ def extendBorder (needle : Array Char) (table : Array Nat) (j : Nat) (c : Char) : Nat := if needle.getD j 'a' = c then j + 1 else if j = 0 then 0 else if h : table.getD (j - 1) 0 < j then extendBorder needle table (table.getD (j - 1) 0) c else 0 termination_by j decreasing_by exact h /-- KMP prefix table: entry `i` is the longest proper border length of the first `i + 1` characters of `needle`. -/ def buildPrefixTable (needle : Array Char) : Array Nat := (needle.foldl (fun st c => let (table, j) := st if table.size = 0 then (#[0], 0) else let j' := extendBorder needle table j c (table.push j', j')) ((#[], 0) : Array Nat × Nat)).1 /-- Scan the remaining haystack characters with `j` needle characters matched and `pos` the current index. -/ def kmpScan (needle : Array Char) (table : Array Nat) (j pos : Nat) : List Char → Option Nat | [] => none | c :: cs => let j' := extendBorder needle table j c if j' = needle.size then some (pos + 1 - needle.size) else kmpScan needle table j' (pos + 1) cs /-- First zero-based index where `needle` matches in `haystack`, scanning left to right with the prefix table. -/ def kmpSearch (needle : Array Char) (table : Array Nat) (haystack : List Char) : Option Nat := if needle.size = 0 then some 0 else kmpScan needle table 0 0 haystack /-! ### Main algorithm (impl) -/ /-- Knuth-Morris-Pratt search: a prefix table over the needle guides one linear scan of the haystack. -/ def findFirstOccurrenceIndex (input : Input) : Output := let needle := input.1.toList.toArray match kmpSearch needle (buildPrefixTable needle) input.2.toList with | some i => (i : Int) | none => -1 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem findFirstOccurrenceIndex_correct (input : Input) (h : isValidInput input) : firstOccurrence_spec input (findFirstOccurrenceIndex input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("sad", "sadbutsad") #guard isValidInput ("leeto", "leetcode") #guard isValidInput ("a", "a") /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("a", "A")) #guard !(isValidInput ("A", "a")) #guard !(isValidInput ("a", "a b")) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard firstOccurrence_check ("sad", "sadbutsad") 0 #guard firstOccurrence_check ("leeto", "leetcode") (-1) #guard firstOccurrence_check ("a", "a") 0 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(firstOccurrence_check ("sad", "sadbutsad") 1) #guard !(firstOccurrence_check ("leeto", "leetcode") 0) #guard !(firstOccurrence_check ("a", "a") 1) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard findFirstOccurrenceIndex ("sad", "sadbutsad") == 0 #guard findFirstOccurrenceIndex ("leeto", "leetcode") == (-1) #guard findFirstOccurrenceIndex ("a", "a") == 0 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard firstOccurrence_check ("sad", "sadbutsad") (findFirstOccurrenceIndex ("sad", "sadbutsad")) #guard firstOccurrence_check ("leeto", "leetcode") (findFirstOccurrenceIndex ("leeto", "leetcode")) #guard firstOccurrence_check ("a", "a") (findFirstOccurrenceIndex ("a", "a")) end PFindTheIndexOfTheFirstOccurrenceInAString