Q:

Searching for a pattern in a given string

0

Sometimes interviewer asks the question to search a pattern in a given string. There are a lot of algorithms to find the pattern, later we will discuss all the algorithms in detail. Here I am using the Naive algorithm (not a smart algorithm) to search a Pattern.

Suppose a given source string is src[0..n-1] and a pattern is pat[0..m-1]. Here to search the pattern for a given string, we need to slide the pattern string (pat) over source string (src) one by one and check for the match. If the match is found, then slides by 1 again to check for subsequent matches.

Example,
Input: src[] = “How are you”
Patteren: pat[] = “are”
Output: Pattern found at index 4

All Answers

need an explanation for this answer? contact us directly to get an explanation for this answer

#include <stdio.h>
#include <string.h>
//Function to search the pattern
void searchPattern(char *pSrcString, char* pPattern)
{
    int lenSrcString = strlen(pSrcString); //Get length of src string
    int lenPatString = strlen(pPattern); //Get length of pattern string
    int srcIndex = 0;
    /* A loop to slide pat[] one by one on src*/
    for (srcIndex = 0; srcIndex <= lenSrcString - lenPatString; ++srcIndex)
    {
        int patternIndex;
        /* For current index i, check for pattern match */
        for (patternIndex = 0; patternIndex < lenPatString; ++patternIndex)
        {
            if (pSrcString[srcIndex + patternIndex] != pPattern[patternIndex])
                break;
        }
        // if pat[0...M-1] = src[srcIndex, srcIndex+1, ...srcIndex+M-1]
        if (patternIndex == lenPatString)
        {
            printf("Pattern found at index %d \n", srcIndex);
        }
    }
}
int main()
{
    char src[] = "How are you"; //source string
    char pat[] = "are"; //pattern you want to find
    searchPattern( src,pat); //function to search pattern
    return 0;
}

Output: Pattern found at index 4.

need an explanation for this answer? contact us directly to get an explanation for this answer

total answers (1)

This question belongs to these collections

Similar questions


need a help?


find thousands of online teachers now