CareerCup

Use pointer to pointing to the start of two string. Compare if match. If yes, move the pointer to PATTERN together with pointer to INPUT. If match not found, reset pointer to PATTERN to the begin.

This change be done in o(n) by modifying Knuth-Morris-Pratt algorithm. The small modification is, if index i in pattern string is *, make next[i+1]=i and i is also the min of next[] for index > i.

Let pattern(array, p[]) be of length M and given string(array, str[]) be of length N. Now,
int findMatchingIndex(char*str, char*p)
{
int i=0, j=0;
for(i=0;i<=N-M+1;i++)
{
if(str[i]==p[i])
{
int xored=1;
for(int j=0;j<M;j++)
{
xored *= str[i+j] ^ p[j];
if(xored==0)
return i; //index of first match
}
}
}
return -1; //not found
}