CareerCup

Most efficient algorithm for sub-string search

http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

Start with 2 pointers, p1 pointing to first character in S1 and p2 to first character in S2. Move p2 till *p2 is equal to *p1. After that, move each pointer by 1 position. As soon as *p1!=*p2, move p1 back to the start. Repeat above till you reach the end of S2.
This will be done in O(n) time

bool IsSubstring(char * search , char * in)
{

int searchlen= strlen (search), inlen= strlen(in);
int it , innerit;
int begin=0;
assert(search !=NULL && in != NULL);
assert(searchlen >0 && searchlen <= inlen);

for(it = 0; it< inlen-searchlen; it++)
{
//if first char of search matches with the current char
if(search[begin] ==in[it])
{
innerit= it+1;
begin++;
//proceed further check for the remaining
while(begin < searchlen)
{
// if any mismatch is found break out of it
if(in[innerit] != search[begin])
{
begin = 0;
break;
}
innerit++;
begin++;
}
// if match was found following condition will be true
if(begin == searchlen)
{
return true;
}
}
}
return false;
}// end of IsSubstring

Knuth Morris is a good algorithm but suffix trees is even a better algorithm if you are going to find a match for many substrings. Knuth Morris processes the substring while suffix trees process the main string.

Knuth Morris is a good algorithm but suffix trees is even a better algorithm if you are going to find a match for many substrings. Knuth Morris processes the substring while suffix trees process the main string.

Complexity:
Knuth Morris: O(n|S| + Si | pi |) time for n queries.

Suffix trees: O(|S| + Si | pi |) time for n queries.

Hence suffix trees is a better option

I cant believe you would mention suffix trees in the interview and get away coding it. I think it very tough to code during the interview. So wisely onely should not give a solution using suffix trees.

i believe , no one will ask you to write code if it is very tough in limited time , so there is nothing wrong in saying suffix tree and you should be in a position to atleast try coding for suffix tree in that limited time in case interviewer would like to know your coding skills , who knows , his intention might be to know from you whether you are aware of "suffix tree " concept or not , if you are not revealing abt it , then he might even think you didnt even know the name "suffix tree " ..