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
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)