# 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.