Pattern Searching

Print Cheatsheet

Naive Pattern Search Iteration

Naive Pattern Search iterates over each character in a text and then counts the following number of matching characters to find the pattern.

Naive Pattern Search Runtime

The worst-case performance of Naive Pattern Search is O(nk) and can approach O(n^2). This is caused by the constant backtracking to the next character in the text after a pattern is not found.

Naive Pattern Match

In Python, a pattern can be matched to a section of text by counting and then comparing the number of identical elements.

Naive Pattern Search Algorithm

Our Python implementation of naive pattern search takes in a text and pattern and prints the indices of the matches if they exist.

def pattern_search(text, pattern):
  for index in range(len(text)):
    match_count = 0
    for char in range(len(pattern)):
      if pattern[char] == text[index + char]:
        match_count += 1
      else:
        break
    if match_count == len(pattern):
      print(pattern, "found at index", index)