Pattern Matching

Pattern Matching (Naive)

Pattern Matching is the process of finding occurrences of a target string (called the pattern, pat) within a larger host string (called the text, text). For example, searching for the pattern "AABA" in the text "AABAACAADAABAABA" reveals matches at indices 0, 9, and 12.

Implementation Mechanics: The Naive Approach

The Naive (Brute Force) pattern matching algorithm is the simplest approach:

1. Alignment: Align the pattern starting at index i = 0 of the text.
2. Scan: Scan characters of the pattern (j = 0 to M - 1) against the aligned segment of the text (text[i + j]).
3. Check:
   • If all characters match (j == M), record a match at index i.
   • If a mismatch is encountered at any point, stop scanning this segment.
4. Shift: Shift the pattern to the right by 1 index (i++) and repeat from step 2.
5. Termination: Stop when the pattern shifts past N - M (where N is text length and M is pattern length), as the remaining text is too short to fit the pattern.

Complexity Analysis

• Time Complexity:
  • Best Case: O(N) (when the first character of the pattern does not match the text at all, e.g., text "AAAAAAAAAA" and pattern "B")
  • Worst Case: O(N * M) (when all characters match except the last, or when text and pattern are highly repetitive, e.g., text "AAAAAAAAAAAAAAAA" and pattern "AAAB")
• Space Complexity: O(1) (constant auxiliary space since we only use index pointers)