Skip to content
TheChatArchiveThe Chat Archive
Grok 4.1 Fast· xaiHugging Face Frontier Reasoning Traces

Create an algorithm for pattern matching using the KMP algorithm.

  1. User

    Create an algorithm for pattern matching using the KMP algorithm.

  2. 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 matches
    

    Explanation

    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 substring pattern[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

    1. Compute LPS:

      • Initialize lps[0] = 0.
      • Use two pointers: i (current end of substring) and length (current LPS length).
      • Expand when characters match; backtrack using lps[length-1] on mismatch.
    2. Search:

      • Traverse text with i and pattern with j.
      • On match: Advance both.
      • On full match (j == m): Record position, set j = lps[j-1] for overlaps.
      • On mismatch: Set j = lps[j-1] (skip redundant checks), advance i if j == 0.

    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.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.