Scribd
Upload
4 views2 pages

Naive String Matching Lab

The document outlines an experiment on naive string matching to find all occurrences of a pattern in a given text. It includes an algorithm, C code implementation, sample input, and output demonstrating the pattern matching. The time complexity is O(n*m) and the space complexity is O(1).

Uploaded by

kingkunalsingh83
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
4 views2 pages

Naive String Matching Lab

The document outlines an experiment on naive string matching to find all occurrences of a pattern in a given text. It includes an algorithm, C code implementation, sample input, and output demonstrating the pattern matching. The time complexity is O(n*m) and the space complexity is O(1).

Uploaded by

kingkunalsingh83
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

Experiment: Naive String Matching

Aim
To find all occurrences of a pattern in a given text using the naive string matching algorithm.

Algorithm
1 Start the program.

2 Input the text string T.

3 Input the pattern string P.

4 Find length of text (n) and pattern (m).

5 Set i = 0.

6 Compare pattern P with substring of T starting at index i.

7 Compare characters one by one.

8 If mismatch occurs, shift pattern by one position.

9 If all characters match, print index i.

10 Increment i and repeat steps until i <= n - m.

11 Display all matching positions.

12 Stop the program.

C Code
#include <stdio.h>
#include <string.h>

void naiveMatch(char text[], char pattern[]) {


int n = strlen(text);
int m = strlen(pattern);

for(int i=0;i<=n-m;i++) {
int j;
for(j=0;j<m;j++) {
if(text[i+j] != pattern[j])
break;
}
if(j==m)
printf("Pattern found at index %d\n", i);
}
}

int main() {
char text[] = "AABAACAADAABAABA";
char pattern[] = "AABA";

naiveMatch(text, pattern);
return 0;
}

Sample Input
Text: AABAACAADAABAABA
Pattern: AABA
Sample Output
Pattern found at index 0
Pattern found at index 9
Pattern found at index 12

Complexity
Time Complexity: O(n*m)
Space Complexity: O(1)

You might also like