Scribd
Upload
6 views4 pages

Naive String Matching Algorithm

The Naive String-Matching Algorithm is a basic technique for finding a pattern within a larger text by comparing characters one by one. It involves aligning the pattern with the text and shifting it right upon mismatches, leading to potentially high computational costs for large inputs. The algorithm has a time complexity of O(n × m) in the worst case and uses constant space.

Uploaded by

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

Naive String Matching Algorithm

The Naive String-Matching Algorithm is a basic technique for finding a pattern within a larger text by comparing characters one by one. It involves aligning the pattern with the text and shifting it right upon mismatches, leading to potentially high computational costs for large inputs. The algorithm has a time complexity of O(n × m) in the worst case and uses constant space.

Uploaded by

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

Naive String Matching Algorithm

1. Introduction
The Naive String-Matching Algorithm is one of the most fundamental and
straightforward techniques used in computer science for pattern searching in strings. The
primary goal of string matching is to find whether a given pattern (P) exists within a
larger text (T) and, if so, to identify all positions where the pattern occurs.

2. Theory
The working principle of the Naive String-Matching Algorithm is based on sliding
window comparison. The pattern is aligned with the beginning of the text, and characters
are compared one by one from left to right.

Working Mechanism:
1. Align the pattern at the start of the text.

2. Compare each character of the pattern with the corresponding character in the
text.

3. If all characters match → pattern found.

4. If any character mismatches → shift the pattern by one position to the right.

5. Repeat the process until the pattern reaches the end of the text.

This method does not use any information from previous comparisons to improve
efficiency, which leads to repeated comparisons and high computational cost for large
inputs.

3. Algorithm Description
Input:

 Text T of length n

 Pattern P of length m

Output:

 All starting positions where pattern P occurs in text T

Algorithm Steps:
1. Read text T and pattern P.

2. Compute lengths n and m.

3. For each position i from 0 to (n − m):

o Compare pattern characters with text characters.

o If all characters match → record position i.

o Otherwise → shift pattern by one position.

4. Continue until all positions are checked.

4. Pseudocode
for i = 0 to n-m:

j=0

while j < m and T[i+j] == P[j]:

j=j+1

if j == m:

print "Pattern found at position", i

5. Apply Naïve String-Matching algorithm for the given


Text T="AABAACAADAABAABA"
Pattern P = "AABA"
Given:

Text T = "AABAACAADAABAABA"
Pattern P = "AABA"

Step-by-step Matching:

Position Substring Match

0 AABA ✓ Match
Position Substring Match

1 ABAA ✗

2 BAAC ✗

3 AACA ✗

4 ACAA ✗

5 CAAD ✗

6 AADA ✗

7 ADAA ✗

8 DAAB ✗

9 AABA ✓ Match

10 ABAA ✗

11 BAAB ✗

12 AABA ✓ Match

Result:

Pattern found at positions: 0, 9, 12

6. Time and Space Complexity


Time Complexity:

 Best Case: O(n)

o When pattern mismatches at the first character itself.

 Worst Case: O(n × m)

o When the pattern and text have repeated characters and full comparison is
done at each position.

 Average Case: O(n × m)


Where:

 n = length of text

 m = length of pattern

Space Complexity:

 O(1) (Constant space)

 No extra memory used apart from variables

You might also like