Geeks for Geeks Tutorial: Naive Algorithm for Pattern Searching

Problem Statement

• Given:
  • Text String of size n
  • Pattern String of size M
• Task: Write a function search that:
  • Takes the text and pattern strings as input
  • Prints all occurrences of the pattern in the text string
  • Assumption: n (text size) is always greater than M (pattern size)

Example

• Text: "this"
• Pattern: "is"
• Output: Indexes in text where the pattern is found: e.g., starting from index 0, index 9, and then next one

Naive Algorithm Approach

1. Window Size: Equal to the size of the pattern string (M)

2. Process:

   • Run a window over the text string starting from index 0
   • Compare the current window with the pattern string
   • If equal, the pattern is found at that index
   • Move the window forward and continue comparison
   • Continue until the last possible window

3. Loop Details:

   • Outer Loop: Runs n - M + 1 times (from index 0 to n-M)
     • Indicates the starting index of the window
   • Inner Loop: Runs for each window (from 0 to M)
     • Compares each character in the window with the pattern

Code Explanation

• Function: search takes text and pattern as input
• Compute lengths of text (n) and pattern (M)
• Outer Loop: Iterates over possible starting indices of the window
• Inner Loop: Compares characters of the window with the pattern
• If no match is found at any point, break out of the loop
• Print index if pattern is found

Complexity Analysis

• Best Case: Pattern's first character is not in text

  • Comparison is minimal, moving window quickly
  • Time Complexity: O(n - M)

• Worst Case: All characters in pattern and text are similar

  • Must compare every character in the pattern with the window
  • Time Complexity: O(M * (n - M + 1))*

Note

• KMP (Knuth-Morris-Pratt) Matching Algorithm: Improves worst-case complexity to O(n)
• KMP algorithm is covered in a separate video

Conclusion

• Naive pattern searching provides a straightforward approach to find pattern occurrences.
• Highlights the need for efficient algorithms like KMP in worst-case scenarios.

• Thank you for watching. Please leave likes and comments.

(Note: This summary covers algorithm explanation and complexity analysis.)