CareerCup

The Knuth-Morris-Pratt or the Morris-Pratt algorithms are extensions of the basic Brute Force algorithm. They use precomputed data to skip forward not by 1 character, but by as many as possible for the search to succeed.

Here is some code

void preComputeData(char *x, int m, int Next[])
{
int i, j;
i = 0;
j = Next[0] = -1;

while (i < m)
{
while (j > -1 && x[i] != x[j])
j = Next[j];
Next[++i] = ++j;

}
}


void MorrisPrat(char *x, int m, char *y, int n)
{
int i, j, Next[1000];

/* Preprocessing */
preComputeData(x, m, Next);

/* Searching */
i = j = 0;
while (j < n)
{
while (i > -1 && x[i] != y[j])
i = Next[i];
i++;
j++;
if (i >= m)
{
printf("\nMatch found at : [%d]\n",j - i);
i = Next[i];
}
}
}


int main()
{
char *string="hereroheroero";
char *pattern="hero";

MorrisPrat(pattern,strlen(pattern),string,strlen(string));

printf("\n\n");
return(0);

}

rabinkarp string searching algorithm

or use suffix trees....could be build in O(n) and searched using O(m)
n =length of base string
m=length of pattern to be searched

use boyer-moore its more effiecient than all string patter matching

I don't think it is a good interview question.

int MyStrStr(char * a,char * b)
{
    int a_p = 0;
    int b_p = 0;
    int ret = -1;
    if(a == NULL || b == NULL)
        return -1;
    while(true)
    {
        if(a[a_p] == '\0')
            break;
        if(a[a_p] == b[0])
        {
            ret = a_p;
            b_p = 0;
            //start check
            while(true)
            {
                if(b[b_p] == '\0')
                    break;
                if(a[a_p+b_p] != b[b_p])
                {
                    return -1;
                }
                b_p++;
            }
        }
        a_p++;
    }
    return ret;
}

char * strstr(const char *s1, const char *s2) {
    const char *a = s1, *b = s2;
    for (;;) {
        if (!*b) return (char *)s1;
        if (!*a) return NULL;
        if (*a++ == *b++) continue;
        a = ++s1;
        b = s2;
    }
}