Naive String Matching Algorithm - AOA module notes

Naïve String Matching Algorithm

The Naïve String Matching Algorithm is a basic technique for searching a pattern within a text. It follows a brute-force approach by checking for the pattern at every possible position in the text.

Working of the Algorithm

1. Let T be the text of length N and P be the pattern of length M.
2. Start comparing P with substrings of T from left to right.
3. If all characters match, the pattern is found at that index.
4. Otherwise, shift the pattern one position to the right and repeat.
5. Continue until the entire text has been scanned.

Time Complexity

Example

Consider the following:

Text (T): "AABAACAADAABAAABAA" (N = 18)

Pattern (P): "AABA" (M = 4)

Step-by-Step Execution:

• Compare P with T[0:3] → "AABA" → Match at index 0 ✅
• Shift and compare P with T[1:4] → "ABAA" → Mismatch ❌
• Shift and compare P with T[2:5] → "BAAC" → Mismatch ❌
• Shift and compare P with T[3:6] → "AACA" → Mismatch ❌
• Shift and compare P with T[9:12] → "AABA" → Match at index 9 ✅
• Shift and compare P with T[13:16] → "AABA" → Match at index 13 ✅

Python Implementation

def naive_string_match(text, pattern):
    N = len(text)
    M = len(pattern)
    matches = []
    
    for i in range(N - M + 1):
        match = True
        for j in range(M):
            if text[i + j] != pattern[j]:
                match = False
                break
        if match:
            matches.append(i)
    
    return matches

# Example usage
text = "AABAACAADAABAAABAA"
pattern = "AABA"
result = naive_string_match(text, pattern)
print("Pattern found at indices:", result)

Output

Pattern found at indices: [0, 9, 13]

Advantages & Disadvantages

✅ Advantages:

• Simple and easy to implement.
• Effective for small-sized text and patterns.

❌ Disadvantages:

• Inefficient for large texts due to O(NM) complexity.
• Not suitable for cases requiring multiple pattern searches.

For larger texts, advanced algorithms like Knuth-Morris-Pratt (KMP) and Boyer-Moore are recommended.