Naive String Matching Algorithm

String Matching Algorithm is also called"String Searching Algorithm." This is a vital class of string algorithm is declared as "this is the method to find a place where one is several strings are found within the larger string."

The naïve approach tests all the possible placement of Pattern P [1.......m] relative to text T [1......n]. We try shift s = 0, 1.......n-m, successively and for each shift s. Compare T [s+1.......s+m] to P [1......m].

The naïve 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 value of s.

NAIVE-STRING-MATCHER (T, P)
 1. n ← length [T]
 2. m ← length [P]
 3. for s ← 0 to n -m
 4. do if P [1.....m] = T [s + 1....s + m]
 5. then print "Pattern occurs with shift" s

Analysis: This for loop from 3 to 5 executes for n-m + 1(we need at least m characters at the end) times and in iteration we are doing m comparisons. So the total complexity is O (n-m+1).

Example:

1. Suppose T = 1011101110  
2.         P = 111  
3.        Find all the Valid Shift  

Solution: