import Mathlib /-! # Number Of Matching Subsequences Given a string s and an array of strings words, return the number of words[i] that is a subsequence of s. A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde". ## Constraints - 1 <= s.length <= 5 * 10^4 - 1 <= words.length <= 5000 - 1 <= words[i].length <= 50 - s and words[i] consist of only lowercase English letters. ## Provided examples - `s = "abcde", words = ["a", "bb", "acd", "ace"]` → `3` - `s = "dsahjpjauf", words = ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]` → `2` - `s = "ababababab", words = ["ab", "aba", "aab", "baba", "babababababab"]` → `4` ## Synthesized negative examples - invalid input: `s = "", words = ["a"]` ([structural] a predicate that admits 1 <= s.length <= 5 * 10^4. empty s; predicate that forgot the nonempty floor accepts it) - invalid input: `s = "a", words = ["abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"]` ([structural] a predicate that admits 1 <= words[i].length <= 50. two letters past word maximum; predicate checking only minimum accepts it) - invalid input: `s = "A", words = ["a"]` ([structural] a predicate that admits s and words[i] consist of only lowercase English letters.. uppercase in s; predicate using isalpha instead of lowercase accepts it) - `s = "abcde", words = ["a", "bb", "acd", "ace"]` → `2` is wrong ([structural] answer required only to be achievable, not maximal. 2 is achievable by two matching words but not maximal) - `s = "dsahjpjauf", words = ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]` → `0` is wrong ([structural] no lower bound requires counting any word. zero is the trivial count accepted by a spec with no work.) - `s = "ababababab", words = ["ab", "aba", "aab", "baba", "babababababab"]` → `3` is wrong ([structural] specification only requires a lower bound, not the exact count. 3 is feasible since four words qualify, but is not maximal) -/ namespace PNumberOfMatchingSubsequences abbrev Input := (String) × (List String) abbrev Output := Nat /-! ### Specification helpers -/ /-- The first string occurs inside the second by deleting characters without reordering. -/ def IsSubsequence (w s : String) : Prop := List.Sublist w.toList s.toList /-- Every character of the string lies between `'a'` and `'z'`. -/ def isLowerLetters (s : String) : Bool := s.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Validity predicate (V) -/ /-- Valid input: the stated size bounds hold and every string is nonempty lowercase. -/ def isValidInput (input : Input) : Bool := let s := input.1 let words := input.2 1 ≤ s.length && s.length ≤ 5 * 10^4 && 1 ≤ words.length && words.length ≤ 5000 && words.all (fun w => 1 ≤ w.length && w.length ≤ 50 && isLowerLetters w) && isLowerLetters s /-! ### Ideal specification (P_spec) -/ /-- `result` counts exactly the indices whose word is a subsequence of the string. -/ def numMatchingSubsequences_spec (input : Input) (result : Output) : Prop := ∃ idx : Finset (Fin input.2.length), idx.card = result ∧ ∀ i : Fin input.2.length, i ∈ idx ↔ IsSubsequence (input.2.get i) input.1 /-! ### Decidable specification (P_check) -/ /-- `IsSubsequence w s` unfolds to `List.Sublist` of the character lists, which Lean decides via the decidable equality on `Char`. -/ instance decidableIsSubsequence (w s : String) : Decidable (IsSubsequence w s) := inferInstanceAs (Decidable (List.Sublist w.toList s.toList)) /-- Decides the existential over `idx : Finset (Fin input.2.length)`: the membership iff forces `idx` to be exactly `Finset.univ.filter (fun i => IsSubsequence (input.2.get i) input.1)`, so existence collapses to the decidable equality of its card with `result`. -/ instance decidableNumMatchingSubsequences (input : Input) (result : Output) : Decidable (∃ idx : Finset (Fin input.2.length), idx.card = result ∧ ∀ i : Fin input.2.length, i ∈ idx ↔ IsSubsequence (input.2.get i) input.1) := decidable_of_iff ((Finset.univ.filter (fun i => IsSubsequence (input.2.get i) input.1)).card = result) (by constructor · intro h exact ⟨Finset.univ.filter (fun i => IsSubsequence (input.2.get i) input.1), h, fun i => by simp [Finset.mem_filter]⟩ · rintro ⟨idx, hcard, hiff⟩ have hset : idx = Finset.univ.filter (fun i => IsSubsequence (input.2.get i) input.1) := by ext i simp only [Finset.mem_filter, Finset.mem_univ, true_and] exact hiff i rw [hset] at hcard exact hcard) /-- Executable checker obtained mechanically from the specification. -/ def numMatchingSubsequences_check (input : Input) (result : Output) : Bool := @decide (numMatchingSubsequences_spec input result) (by unfold numMatchingSubsequences_spec; infer_instance) /-- On valid input the checker accepts exactly the specified outputs. -/ theorem numMatchingSubsequences_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : numMatchingSubsequences_check input result ↔ numMatchingSubsequences_spec input result := by simp [numMatchingSubsequences_check] /-! ### Implementation helpers -/ /-- Next-occurrence table of `s`: row `i` maps a lowercase letter to its first index at or after `i`, if any. -/ def buildNextTable (s : String) : Array (Array (Option Nat)) := let cs := s.toList.toArray let emptyRow := Array.replicate 26 (none : Option Nat) let rec go (i : Nat) (row : Array (Option Nat)) (rows : List (Array (Option Nat))) : List (Array (Option Nat)) := match i with | 0 => rows | i + 1 => let row' := match cs[i]? with | some c => row.setIfInBounds (c.toNat - 'a'.toNat) (some i) | none => row go i row' (row' :: rows) (go cs.size emptyRow [emptyRow]).toArray /-- Decides whether `w` is a subsequence of the string whose next-occurrence table is `table`. -/ def isSubsequenceFast (table : Array (Array (Option Nat))) (w : String) : Bool := let rec go (pos : Nat) (cs : List Char) : Bool := match cs with | [] => true | c :: rest => match table[pos]? with | some row => match row[c.toNat - 'a'.toNat]? with | some (some nxt) => go (nxt + 1) rest | _ => false | none => false go 0 w.toList /-! ### Main algorithm (impl) -/ /-- Counts matching words via a precomputed next-occurrence table, one O(|w|) lookup scan per word. -/ def countMatchingSubsequences (input : Input) : Output := let table := buildNextTable input.1 List.countP (fun w => isSubsequenceFast table w) input.2 /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem countMatchingSubsequences_correct (input : Input) (h : isValidInput input) : numMatchingSubsequences_spec input (countMatchingSubsequences input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput ("abcde", ["a", "bb", "acd", "ace"]) #guard isValidInput ("dsahjpjauf", ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]) #guard isValidInput ("ababababab", ["ab", "aba", "aab", "baba", "babababababab"]) /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput ("", ["a"])) #guard !(isValidInput ("a", ["abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyz"])) #guard !(isValidInput ("A", ["a"])) /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard numMatchingSubsequences_check ("abcde", ["a", "bb", "acd", "ace"]) 3 #guard numMatchingSubsequences_check ("dsahjpjauf", ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]) 2 #guard numMatchingSubsequences_check ("ababababab", ["ab", "aba", "aab", "baba", "babababababab"]) 4 /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(numMatchingSubsequences_check ("abcde", ["a", "bb", "acd", "ace"]) 2) #guard !(numMatchingSubsequences_check ("dsahjpjauf", ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]) 0) #guard !(numMatchingSubsequences_check ("ababababab", ["ab", "aba", "aab", "baba", "babababababab"]) 3) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard countMatchingSubsequences ("abcde", ["a", "bb", "acd", "ace"]) == 3 #guard countMatchingSubsequences ("dsahjpjauf", ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]) == 2 #guard countMatchingSubsequences ("ababababab", ["ab", "aba", "aab", "baba", "babababababab"]) == 4 /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard numMatchingSubsequences_check ("abcde", ["a", "bb", "acd", "ace"]) (countMatchingSubsequences ("abcde", ["a", "bb", "acd", "ace"])) #guard numMatchingSubsequences_check ("dsahjpjauf", ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"]) (countMatchingSubsequences ("dsahjpjauf", ["ahjpjau", "ja", "ahbwzgqnuk", "tnmlanowax"])) #guard numMatchingSubsequences_check ("ababababab", ["ab", "aba", "aab", "baba", "babababababab"]) (countMatchingSubsequences ("ababababab", ["ab", "aba", "aab", "baba", "babababababab"])) end PNumberOfMatchingSubsequences