The naive string-matching algorithm

The naive string-matching algorithm

The naive algorithm finds all valid shifts using a loop that checks the condition P [1. .m] = T [s + 1 . . s + m] for each of the n - m + 1 possible values of s.

The above figure shows naïve string matching algorithm for the pattern P = aab and the text T = acaabc .

In figure (a)–(d) are the four successive alignments tried by the naive string matcher. In each part, vertical lines connect corresponding regions found to match (shown shaded), and a jagged line connects the first mismatched character found.

The algorithm finds one occurrence of the pattern, at shift s = 2, shown in part (c) of the figure

Procedure NAIVE-STRING-MATCHER takes time O((n - m + 1) m), and this bound is tight in the worst case. NAIVE-STRING-MATCHER is not an optimal procedure for this problem.

Naïve string matching algorithm is simple, it does not require any preprocessing. It always shifts the window by exactly one position to right.