Searching for Patterns

Source

Given a text txt[0..n-1] and a pattern pat[0..m-1], write a function search(char pat[], char txt[]) that prints all occurrences of pat[] in txt[]. You may assume that n > m.

Examples:
1) Input:

  txt[] =  "THIS IS A TEST TEXT"   pat[] = "TEST" 

Output:

Pattern found at index 10

2) Input:

  txt[] =  "AABAACAADAABAAABAA"   pat[] = "AABA" 

Output:

   Pattern found at index 0    Pattern found at index 9    Pattern found at index 13 

Pattern searching is an important problem in computer science. When we do search for a string in notepad/word file or browser or database, pattern searching algorithms are used to show the search results.

Naive Pattern Searching:
Slide the pattern over text one by one and check for a match. If a match is found, then slides by 1 again to check for subsequent matches.

?

#include #include 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 program to test above function */ int main() { char *txt = "AABAACAADAABAAABAA"; char *pat = "AABA"; search(pat, txt); getchar(); return 0; }

?