C Program for Naive Pattern Searching Algorithm
Slide the pattern over text one by one and check for a match. If a match is found, then slide by 1 again to check for subsequent matches.
C
// C program for Naive Pattern Searching algorithm #include <stdio.h> #include <string.h> void search( char * pat, char * txt) { int M = strlen (pat); int N = strlen (txt); /* A loop to slide pat[] one by one */ for ( int i = 0; i <= N - M; i++) { int j; /* For current index i, check for pattern match */ for (j = 0; j < M; j++) if (txt[i + j] != pat[j]) break ; if (j == M) // if pat[0...M-1] = txt[i, i+1, ...i+M-1] printf ( "Pattern found at index %d \n" , i); } } // Driver's code int main() { char txt[] = "AABAACAADAABAAABAA" ; char pat[] = "AABA" ; // Function call search(pat, txt); return 0; } |
Pattern found at index 0 Pattern found at index 9 Pattern found at index 13
Time Complexity: O(N2)
Auxiliary Space: O(1)
C Program for Naive algorithm for Pattern Searching
Write a C program for a given text string with length n and a pattern with length m, the task is to print all occurrences of the pattern in text.
Note: You may assume that n > m.
Examples:
Input: text = “THIS IS A TEST TEXT”, pattern = “TEST”
Output: Pattern found at index 10Input: text = “AABAACAADAABAABA”, pattern = “AABA”
Output: Pattern found at index 0, Pattern found at index 9, Pattern found at index 12