String Searching Algorithms

Welcome to this insightful lesson on string searching algorithms, a core part of programming often used in software development, database design, and information retrieval. Today, we’ll introduce you to one of the most efficient approaches — the Knuth-Morris-Pratt (KMP) algorithm.

The KMP algorithm optimizes string searching by avoiding unnecessary backtracking. Rather than re-checking characters in the text, it uses a precomputed array called the Longest Prefix Suffix (LPS) array to skip over parts that have already been matched. Here’s the code:

def kmp_search(text, pattern)
  # Helper function to compute the Longest Prefix Suffix (LPS) array
  def compute_lps(pattern)
    lps = Array.new(pattern.length, 0)
    length = 0
    i = 1

    # Build the LPS array for the pattern
    while i < pattern.length
      if pattern[i] == pattern[length]
        length += 1
        lps[i] = length
        i += 1
      else
        # If there's a mismatch and we have a prefix match, use the LPS
        length = length != 0 ? lps[length - 1] : 0
        i += 1 if length == 0
      end
    end
    lps
  end

  # Compute the LPS array and initialize pointers for text and pattern
  lps = compute_lps(pattern)
  i = j = 0

  # Search for the pattern within the text
  while i < text.length
    if pattern[j] == text[i]
      i += 1
      j += 1
    end

    # If we reached the end of the pattern, we found a match
    return i - j if j == pattern.length

    # If there's a mismatch after some matches
    if i < text.length && pattern[j] != text[i]
      j = j != 0 ? lps[j - 1] : 0
      i += 1 if j == 0
    end
  end

  -1  # Return -1 if no match is found
end

# Test
puts kmp_search("abxabcabcaby", "abcaby")  # Output: 6

Here's what's happening in the above code:

1. The compute_lps function builds the Longest Prefix Suffix (LPS) array for the pattern, helping determine skips in case of mismatches. For each character, if it matches the previous prefix, length is incremented; otherwise, it resets to avoid redundant checks.

2. The main function then uses this array to match characters in pattern and text. On mismatches, it leverages lps to skip parts of the pattern, avoiding unnecessary comparisons.

This example shows how KMP efficiently finds the first occurrence of pattern in text. Let me know if you have any questions about a specific part of the algorithm!