Jun 22, 2009

How do you find out if a given string S1 is a substring of another string S2? Provide algorithm, code and test cases.

How do you find out if a given string S1 is a substring of another string S2? Provide algorithm, code and test cases.
Kmp algorithm
bool kmp(char* str1, char* str2)
{
int p1=p2=0;
int n1=0;
while(str1[p1]!='\0')
{
while(str2[p2]!='\0')
{
if(str1[p1]==str2[0])
n1=p1;
if(str1[p1]==str2[p2])
{
p1++;
p2++;
}
else break;
}
if(str2[p2]=='\0')
return true;
else
{
p2=0;
if(n1!=0) p1=n1;
else p1++;
n1=0;
}
}
return false;
}

No comments:

Post a Comment