C Programming-Searching for Patterns Set 1 Naive Pattern Searching

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:

Input:  txt[] = "THIS IS A TEST TEXT"
        pat[] = "TEST"
Output: Pattern found at index 10

Input:  txt[] =  "AABAACAADAABAABA"
        pat[] =  "AABA"
Output: Pattern found at index 0
        Pattern found at index 9
        Pattern found at index 12

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.

C Programming

[pastacode lang=”c” manual=”%2F%2F%20C%20program%20for%20Naive%20Pattern%20Searching%20algorithm%0A%23include%3Cstdio.h%3E%0A%23include%3Cstring.h%3E%0A%20%0Avoid%20search(char%20*pat%2C%20char%20*txt)%0A%7B%0A%20%20%20%20int%20M%20%3D%20strlen(pat)%3B%0A%20%20%20%20int%20N%20%3D%20strlen(txt)%3B%0A%20%20%0A%20%20%20%20%2F*%20A%20loop%20to%20slide%20pat%5B%5D%20one%20by%20one%20*%2F%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%3D%20N%20-%20M%3B%20i%2B%2B)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20j%3B%0A%20%20%0A%20%20%20%20%20%20%20%20%2F*%20For%20current%20index%20i%2C%20check%20for%20pattern%20match%20*%2F%0A%20%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%20M%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20(txt%5Bi%2Bj%5D%20!%3D%20pat%5Bj%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%3B%0A%20%0A%20%20%20%20%20%20%20%20if%20(j%20%3D%3D%20M)%20%20%2F%2F%20if%20pat%5B0…M-1%5D%20%3D%20txt%5Bi%2C%20i%2B1%2C%20…i%2BM-1%5D%0A%20%20%20%20%20%20%20%20%20%20%20printf(%22Pattern%20found%20at%20index%20%25d%20%5Cn%22%2C%20i)%3B%0A%20%20%20%20%7D%0A%7D%0A%20%20%0A%2F*%20Driver%20program%20to%20test%20above%20function%20*%2F%0Aint%20main()%0A%7B%0A%20%20%20char%20txt%5B%5D%20%3D%20%22AABAACAADAABAAABAA%22%3B%0A%20%20%20char%20pat%5B%5D%20%3D%20%22AABA%22%3B%0A%20%20%20search(pat%2C%20txt)%3B%0A%20%20%20return%200%3B%0A%7D” message=”C” highlight=”” provider=”manual”/] [ad type=”banner”]