Grok 4.1 Fast· xai
Frontier Reasoning Traces
Create an algorithm for pattern matching using the KMP algorithm.
- User
Create an algorithm for pattern matching using the KMP algorithm.
- Assistant
def compute_lps(pattern): """ Compute the Longest Proper Prefix which is also Suffix (LPS) array for the pattern. Args: pattern (str): The pattern string to match. Returns: list: LPS array where lps[i] is the length of the longest proper prefix which is also suffix for pattern[0..i]. """ m = len(pattern) lps = [0] * m length = 0 # Length of the previous longest prefix suffix i = 1 while i < m: if pattern[i] == pattern[length]: length += 1 lps[i] = length i += 1 else: if length != 0: length = lps[length - 1] else: lps[i] = 0 i += 1 return lps def kmp_search(text, pattern): """ KMP (Knuth-Morris-Pratt) algorithm for pattern matching. Args: text (str): The text to search in. pattern (str): The pattern to find. Returns: list: List of starting indices where pattern matches in text. """ n = len(text) m = len(pattern) if m == 0: return [] if n == 0: return [] lps = compute_lps(pattern) matches = [] i = 0 # Index for text j = 0 # Index for pattern while i < n: if pattern[j] == text[i]: i += 1 j += 1 if j == m: matches.append(i - j) # Found a match j = lps[j - 1] # Continue to find overlapping matches elif i < n and pattern[j] != text[i]: if j != 0: j = lps[j - 1] else: i += 1 return matchesExplanation
Key Concepts
- LPS Array (Longest Proper Prefix-Suffix): For a pattern,
lps[i]stores the length of the longest proper prefix that is also a suffix for the substringpattern[0..i]. This avoids re-checking characters already matched when a mismatch occurs. - Efficiency: Preprocessing the pattern takes O(m) time. Searching takes O(n) time. Total: O(n + m).
Algorithm Steps
-
Compute LPS:
- Initialize
lps[0] = 0. - Use two pointers:
i(current end of substring) andlength(current LPS length). - Expand when characters match; backtrack using
lps[length-1]on mismatch.
- Initialize
-
Search:
- Traverse text with
iand pattern withj. - On match: Advance both.
- On full match (
j == m): Record position, setj = lps[j-1]for overlaps. - On mismatch: Set
j = lps[j-1](skip redundant checks), advanceiifj == 0.
- Traverse text with
Example
text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" LPS for pattern: [0, 0, 1, 2, 0, 1, 2, 3, 2] (computed via compute_lps) Matches at indices: [10, 12]text[10:19] = "ABABCABAB"(exact match).- Overlaps allow efficient detection.
Usage
text = "ABABDABACDABABCABAB" pattern = "ABABCABAB" print(kmp_search(text, pattern)) # Output: [10, 12]This implementation handles edge cases (empty strings, no matches) and finds all overlapping occurrences.
- LPS Array (Longest Proper Prefix-Suffix): For a pattern,
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.