Back to course

Lesson 56: String Matching Algorithms: Introduction to Naive Approach

Algorithms: From Zero to Hero (A Beginner's Guide)

56. String Matching Algorithms: Introduction to Naive Approach

String matching is the problem of finding occurrences of a 'pattern' string P within a larger 'text' string T.

The Naive Algorithm

The simplest approach is the brute-force method, where we check every possible position in the text where the pattern might begin.

  1. Start at index i = 0 in the Text T.
  2. Compare the Pattern P (of length M) character by character with the substring of T starting at i.
  3. If all characters match, a match is found.
  4. If a mismatch occurs, shift the pattern by one position (increment i) and start the comparison again.

Efficiency

If the Text length is N and the Pattern length is M:

  • Worst Case Time: O(N * M).
    • This occurs if the pattern and text almost match at every position (e.g., Text = 'AAAAAB', Pattern = 'AAAB'). The algorithm performs nearly M comparisons N times.

For practical, faster string matching, more advanced algorithms like KMP or Rabin-Karp are necessary.