Scribd
Upload
59 views2 pages

Naive String Matching Algorithm Explained

The Naive String Matching Algorithm checks all possible placements of a pattern P within a text T by shifting and comparing substrings. It operates with a time complexity of O(n-m+1) due to the nested loop structure that performs m comparisons for each shift. An example is provided to illustrate the algorithm's application with specific text and pattern values.

Uploaded by

debasish.samal36
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
59 views2 pages

Naive String Matching Algorithm Explained

The Naive String Matching Algorithm checks all possible placements of a pattern P within a text T by shifting and comparing substrings. It operates with a time complexity of O(n-m+1) due to the nested loop structure that performs m comparisons for each shift. An example is provided to illustrate the algorithm's application with specific text and pattern values.

Uploaded by

debasish.samal36
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

26/12/2022, 09:44 DAA Naive String Matching Algorithm - javatpoint

The Naive String Matching Algorithm


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:

Suppose T = 1011101110
P = 111
Find all the Valid Shift

Solution:

[Link] 2/8
26/12/2022, 09:44 DAA Naive String Matching Algorithm - javatpoint

[Link] 3/8

You might also like