Microsoft Interview Question
Software Engineer / DevelopersTeam: Bing
Country: India
Interview Type: In-Person
findstr(char *sub, char *str)
{
if(sub>str || strlen(str)==0 || strlen(sub)==0) {return(-1);}
for(int i=0;i<strlen(str);i++)
{
if(sub[0]==str[i])
{
int k=0, flag=0;
for (int j=i;j<(i+strlen(sub))
{
if (sub[k]==str[i])
{
flag++;
}
k++;
}
if(flag==strlen(sub))
{
printf("substring found at index %d",i);
}
}
}
}
findstr(char *sub, char *str)
{
if(sub>str || strlen(str)==0 || strlen(sub)==0) {return(-1);}
for(int i=0;i<strlen(str);i++)
{
if(sub[0]==str[i])
{
int k=0, flag=0;
for (int j=i;j<(i+strlen(sub))
{
if (sub[k]==str[i])
{
flag++;
}
k++;
}
if(flag==strlen(sub))
{
printf("substring found at index %d",i);
}
}
}
}
void findOccurences(char *substr, char *str){
char *p = str;
int i, j, lenSubStr = strlen(substr), w =strlen(str);
j = 0;
while(j < w-lenSubStr+1){
printf("Starting search at:%s\n",p);
for(i=0;i<lenSubStr;i++){
if((char)p[i] != (char)substr[i]){
printf("break\n");
break;
}
}
if(i == lenSubStr)
printf("Match found at: %d\n",j);
p +=1;
++j;
}
}
O(n^2) Exhaustive search.
Prints multiple occurrences of any substring.
package career.cup;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class SearchSubStringInBigString
{
public static void main(String[] args)
{
String S="hiwtwrwbbhimhdbghimnhhi";
Pattern p1=Pattern.compile("hi");
Matcher m1=p1.matcher(S);
int count=0;
while(m1.find())
{
System.out.print(m1.start()+":"+m1.group()+" ");
if(m1.group().equals("hi"))
{
count++;
}
}
System.out.println();
System.out.println("It is reapting "+count+" times");
}
}
You need to use the KMP algorithm.. to find a substring in a given string. the complexity of it will be O(n)
- Anonymous February 23, 2012