Naive String Matching Algorithm:

The Naive String Matching algorithm is a simple and straightforward approach for finding occurrences of a pattern within a text. It involves systematically comparing the pattern with all possible substrings of the text.

Algorithm Steps:

1.    Initialization:

·        Start with the first character of the text.

2.    Comparison:

·        Compare the pattern with the current substring of the text.

3.    Shift:

·        Move to the next character in the text.

4.    Repeat:

·        Repeat steps 2-3 until the end of the text is reached.

5.    Pattern Match:

·        If a match is found, record the position or perform the required action.

6.    Shift the Pattern:

·        Move the pattern to the next position and repeat the process.

Example:

Consider the text: "ABABCABABABCABABABC" and the pattern: "ABAB".

Algorithm Execution:

1.    Initialization:

·        Start with the first character of the text: "A".

2.    Comparison:

·        Compare "A" with the pattern "ABAB". No match.

3.    Shift:

·        Move to the next character in the text: "B".

4.    Repeat:

·        Compare "B" with the pattern "ABAB". No match.

·        Move to the next character: "A".

5.    Pattern Match:

·        Compare "A" with the pattern "ABAB". No match.

6.    Shift the Pattern:

·        Move the pattern to the next position: "BABA".

7.    Repeat:

·        Continue the process until the end of the text.

8.    Pattern Match:

·        At positions 2, 7, and 12, the pattern "ABAB" matches substrings in the text.

Result:

  • Matches found at positions 2, 7, and 12 in the text.

The Naive String Matching algorithm is simple but may not be the most efficient for large texts. It has a time complexity of O((n-m+1)m), where n is the length of the text and m is the length of the pattern.