import Mathlib /-! # Repeated Substring Pattern Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. ## Constraints - 1 <= s.length <= 10^4 - s consists of lowercase English letters. ## Provided examples - `s = "abab"` → `true` - `s = "aba"` → `false` - `s = "abcabcabcabc"` → `true` ## Synthesized negative examples - invalid input: `s = ""` ([structural] a predicate that admits 1 <= s.length <= 10^4. empty where at least one character is required) - invalid input: `s = "A"` ([structural] a predicate that admits s consists of lowercase English letters.. uppercase; a predicate checking for letters but not case accepts it) - invalid input: `s = " "` ([structural] a predicate that admits s consists of lowercase English letters.. whitespace; a predicate trimming before validating accepts it) - `s = "abab"` → `false` is wrong ([structural] requires at least three copies instead of two. abab has only two copies of ab, so a three-copy threshold rejects it) - `s = "aba"` → `true` is wrong ([structural] multiple copies misread as at least one; substring equal to s qualifies. whole string is a substring repeated once) - `s = "abcabcabcabc"` → `false` is wrong ([structural] only recognizes the degenerate case of a single repeated character. s is not all one character, so false) -/ namespace PRepeatedSubstringPattern abbrev Input := String abbrev Output := Bool /-! ### Specification helpers -/ /-- `s` is some non-empty pattern string appended to itself at least twice. -/ def IsRepeatedSubstringPattern (s : String) : Prop := ∃ p : String, p ≠ "" ∧ ∃ n : Nat, n ≥ 2 ∧ s = String.join (List.replicate n p) /-! ### Validity predicate (V) -/ /-- Valid input: a nonempty string of at most 10^4 lowercase English letters. -/ def isValidInput (input : Input) : Bool := 1 ≤ input.length && input.length ≤ 10^4 && input.toList.all (fun c => 'a' ≤ c && c ≤ 'z') /-! ### Ideal specification (P_spec) -/ /-- `result` is true exactly when `input` is built from multiple copies of a non-empty substring. -/ def repeatedSubstringPattern_spec (input : Input) (result : Output) : Prop := result ↔ IsRepeatedSubstringPattern input /-! ### Decidable specification (P_check) -/ /-- Executable checker for `repeatedSubstringPattern_spec`, searching candidate pattern lengths up to `input.length` with the copy count computed from the length. -/ def repeatedSubstringPattern_check (input : Input) (result : Output) : Bool := result == decide (∃ d : Fin (input.length + 1), 1 ≤ d.val ∧ 2 ≤ input.length / d.val ∧ input = String.join (List.replicate (input.length / d.val) (String.ofList (input.toList.take d.val)))) theorem beq_decide_iff_iff {q : Prop} [Decidable q] (result : Bool) : (result == decide q) = true ↔ (result = true ↔ q) := by cases result <;> simp theorem length_join_replicate (p : String) (n : Nat) : (String.join (List.replicate n p)).length = n * p.length := by rw [String.length_join, List.map_replicate, List.sum_replicate_nat] theorem take_join_replicate (p : String) (n : Nat) (hn : 1 ≤ n) : String.ofList ((String.join (List.replicate n p)).toList.take p.length) = p := by obtain ⟨n', rfl⟩ : ∃ n', n = n' + 1 := ⟨n - 1, by omega⟩ rw [List.replicate_succ, String.toList_join, List.flatMap_cons, List.take_left' (String.length_toList (s := p))] exact String.ofList_toList theorem check_iff_key (input : Input) : (∃ d : Fin (input.length + 1), 1 ≤ d.val ∧ 2 ≤ input.length / d.val ∧ input = String.join (List.replicate (input.length / d.val) (String.ofList (input.toList.take d.val)))) ↔ IsRepeatedSubstringPattern input := by unfold IsRepeatedSubstringPattern constructor · rintro ⟨d, hd1, hd2, hd3⟩ have hdlt := d.isLt have hdle : d.val ≤ input.toList.length := by rw [String.length_toList]; omega refine ⟨String.ofList (input.toList.take d.val), ?_, input.length / d.val, hd2, hd3⟩ intro hc have hz : (String.ofList (input.toList.take d.val)).length = 0 := by rw [hc, String.length_empty] rw [String.length_ofList, List.length_take_of_le hdle] at hz omega · rintro ⟨p, hp, n, hn, hpn⟩ have hlen : input.length = n * p.length := by rw [hpn]; exact length_join_replicate p n have hplen : 1 ≤ p.length := by rcases Nat.eq_zero_or_pos p.length with h0 | h0 · exact absurd (String.length_eq_zero_iff.mp h0) hp · exact h0 have hdvd : input.length / p.length = n := by rw [hlen]; exact Nat.mul_div_cancel n hplen have hple : p.length ≤ input.length := by rw [hlen]; exact Nat.le_mul_of_pos_left p.length (by omega : 0 < n) have hbound : p.length < input.length + 1 := by omega refine ⟨⟨p.length, hbound⟩, hplen, ?_, ?_⟩ · rw [hdvd]; omega · show input = String.join (List.replicate (input.length / p.length) (String.ofList (input.toList.take p.length))) rw [hdvd, hpn, take_join_replicate p n (by omega : 1 ≤ n)] /-- On valid input the checker accepts exactly the specified outputs. -/ theorem repeatedSubstringPattern_check_iff_spec (input : Input) (result : Output) (h : isValidInput input) : repeatedSubstringPattern_check input result ↔ repeatedSubstringPattern_spec input result := by unfold repeatedSubstringPattern_check repeatedSubstringPattern_spec exact (beq_decide_iff_iff result).trans (iff_congr Iff.rfl (check_iff_key input)) /-! ### Implementation helpers -/ /-- The proper divisors of `n`, by trial division up to `sqrt n`, adding both `d` and `n / d` when `d` divides `n`. -/ def properDivisors (n : Nat) : List Nat := (List.range' 1 n).foldr (fun d acc => if d * d > n then acc else if n % d == 0 then let q := n / d if q == d then d :: acc else if q == n then d :: acc else d :: q :: acc else acc) [] /-- Whether `s` equals its length-`d` prefix repeated `s.length / d` times. -/ def matchesPeriod (s : String) (d : Nat) : Bool := s == String.join (List.replicate (s.length / d) (String.ofList (s.toList.take d))) /-! ### Main algorithm (impl) -/ /-- Decides the repeated-substring predicate by testing only the proper divisors of the string length as candidate period lengths. -/ def isRepeatedSubstringPattern (input : Input) : Output := let n := input.length if n < 2 then false else (properDivisors n).any (fun d => matchesPeriod input d) /-! ### Correctness -/ /-- On valid input the algorithm meets the specification. -/ theorem isRepeatedSubstringPattern_correct (input : Input) (h : isValidInput input) : repeatedSubstringPattern_spec input (isRepeatedSubstringPattern input) := by sorry /-! ## Unit tests -/ /-! ### L1 — Validity guard (V accepts the provided examples) -/ #guard isValidInput "abab" #guard isValidInput "aba" #guard isValidInput "abcabcabcabc" /-! ### L1b — Negative validity (V rejects invalid input) -/ #guard !(isValidInput "") #guard !(isValidInput "A") #guard !(isValidInput " ") /-! ### L2 — Specification guard (P_check accepts the correct output) -/ #guard repeatedSubstringPattern_check "abab" true #guard repeatedSubstringPattern_check "aba" false #guard repeatedSubstringPattern_check "abcabcabcabc" true /-! ### L2b — Negative specification (P_check rejects a wrong output) -/ #guard !(repeatedSubstringPattern_check "abab" false) #guard !(repeatedSubstringPattern_check "aba" true) #guard !(repeatedSubstringPattern_check "abcabcabcabc" false) /-! ### L3 — Algorithm output (impl matches the expected output) -/ #guard isRepeatedSubstringPattern "abab" == true #guard isRepeatedSubstringPattern "aba" == false #guard isRepeatedSubstringPattern "abcabcabcabc" == true /-! ### L4 — Integration (P_check certifies the output of impl) -/ #guard repeatedSubstringPattern_check "abab" (isRepeatedSubstringPattern "abab") #guard repeatedSubstringPattern_check "aba" (isRepeatedSubstringPattern "aba") #guard repeatedSubstringPattern_check "abcabcabcabc" (isRepeatedSubstringPattern "abcabcabcabc") end PRepeatedSubstringPattern