Naive String Matching Algorithm

Working Mechanism

• This is simple and efficient brute force approach. It compares the first character of pattern with searchable text. If a match is found, pointers in both strings are advanced. If a match is not found, the pointer to text is incremented and pointer of the pattern is reset. This process is repeated till the end of the text.
• The naïve approach does not require any pre-processing. Given text T and pattern P, it directly starts comparing both strings character by character.
• After each comparison, it shifts pattern string one position to the right.
• Following example illustrates the working of naïve string matching algorithm. Here,
  T = PLANINGANDANALYASIS and P = AND
• Here, t_i and p_j are indices of text and pattern respectively.

Step 1: T[1] ≠ P[1], so advance text pointer, i.e. t_i++.

Step 2 : T[2] ≠ P[1], so advance text pointers i.e. t_i++

Step 3 : T[3] = P[1], so advance both pointers i.e. t_i++, p_j++

Step 4 : T[4] = P[2], so advance both pointers, i.e. t_i++, p_j++

Step 5 : T[5] ≠ P[3], so advance text pointer and reset pattern pointer, i.e. t_i++, p_j = 1

Step 6 : T[6] ≠ P[1], so advance text pointer, i.e. t_i++

Step 7: T[7] ≠ P[1], so advance text pointer i.e. t_i++

Step 8 : T[8] = P[1], so advance both pointers, i.e. t_i++, p_j++

Step 9 :   T[9] = P[2], so advance both pointers, i.e. t_i++, p_j++

Step 10 : T[10] = P[3], so advance both pointers, i.e. t_i++, p_j++

This process continues till the possible comparison in the text string.

Algorithm

Algorithm for naïve string matching approach is described below :

Algorithm  NAÏVE_STRING_MATCHING(T, P)
// T is the text string of length n
// P is the pattern of length m

for  i ← 0 to n – m  do
    if P[1… m] == T[i+1…i+m]  them
        print  “Match Found”
    end
end

Complexity Analysis

There are two cases of consideration :

(i)     Pattern found

• The worst case occurs when the pattern is at last position and there are spurious hits all the way. Example, T = AAAAAAAAAAB, P = AAAB.
• To move pattern one position right, m comparisons are made. Searchable text in T has a length (n – m). Hence, in worst case algorithm runs in O(m*(n – m)) time.

(ii)   Pattern not found 

• In the best case, the searchable text does not contain any of the prefixes of the pattern. Only one comparison requires moving pattern one position right.

Example, T = ABABCDBCAC, P = XYXZ. The algorithm does O(n – m) comparisons.

• In the worst case, first (m – 1) characters of pattern and text are matched and only last character does not match.

Example, T = AAAAAAAAAAAAC, P = AAAAB. Algorithm takes O(m*(n – m)) time.

Some Popular String Matching Algorithms:

• Naive String Matching Algorithm
• String Matching with Automata
• Rabin Karp String Matching Algorithm
• KMP String Matching Algorithm