**Naive String Matching Algorithm**

Naive String Matching Algorithm is the important topic of the Analysis & Design of Algorithm. Moreover, freestudy9 has all kind of important information and topic related to it.

- The string-matching problem is defined as follows.
- We assume that the text is an array T [1…n] of length n and that the pattern is an array P [1…m] of length m ≤ n.
- We further assume that the elements of P and T are characters drawn from a finite alphabet Σ. For example, we may have Σ = {0, 1} or Σ = {a, b …, z}.
- The character arrays P and T often called strings of characters.
- We say that pattern P occurs with shift s in text T (or, equivalently, that pattern P occurs beginning at position s + 1 in text T) if 0 ≤ s ≤ n – m and T [s + 1…s + m] = P [1…m] (that is, if T [s + j] = P[j], for 1 ≤ j ≤ m).
- If P occurs with shift s in T, then we call s a valid shift; otherwise, we call s an invalid shift. The string matching problem is the problem of finding all valid shifts with which a given pattern P occurs in a given text T.
- 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.

#### NAIVE-STRING-MATCHER(T, P)

- n ← length[T]
- m ← length[P]
**for**s ← 0**to**n–m**do****if**P[1,…, m] == T[s + 1,…, s + m]**then**print “Pattern occurs with shift” s

- The naive string-matching procedure can be interpreted graphically as sliding a “template” containing the pattern over the text, noting for which shifts all of the characters on the template equal the corresponding characters in the text, as illustrated in Figure.
- The for loop beginning on line 3 considers each possible shift explicitly.
- The test on line 4 determines whether the current shift is valid or not; this test involves an implicit loop to check corresponding character positions until all positions match successfully or a mismatch found.
- Line 5 prints out each valid shift s.

**Example for Naive String Matching Algorithm**

- In the above example, the valid shift is s = 3 for which we found the occurrence of pattern P in text T.
- Procedure NAIVE-STRING-MATCHER takes time O ((n-m + 1) m), and this bound is tight in the worst case. The running time of NAIVE-STRING- MATCHER is equal to its matching time since there is no preprocessing.

**Related Terms**

ADA Algorithms, Travelling Salesman Problem, Knapsack Problem using Backtracking, Minmax Principle

## Leave a Reply