|
Given two strings, find the number of occurrences of one within the other ....
Software QA/Tests Interview Questions from Microsoft
(Continued from previous question...)
Given two strings, find the number of occurrences of one within the other ....
Question:
Given two strings, find the number of occurrences of one within the other . eg s1=" the cow ran over the dog" s2="the" answer =2. Also, take care of repetitions eg. if s1= "ABCBCBC" and s2="BCBC" then answer=2
maybe an answer:
#include<stdio.h>
#include<string.h>
int f[100];
void fail(char *pat)
{
int i, j, l;
l = strlen(pat);
for(j=1;j<l;j++)
{
if(pat[j] = pat[i+1] && i>=0)
i = f[i];
else if (pat[j] = pat[i+1])
f[j] = i+1;
else
f[j] = -1;
}
return ;
}
int pm(char *str, char *pat)
{
int i,j,l1,l2;
l1 = strlen(str);
l2= strlen(pat);
i = j = 0;
while(i<l1 && j < l2)
{
if(str[i] == pat[j] )
{i++;j++;}
else if (j == 0)i++;
else
{
j = f[j-1]+1;
i++;
}
if(j == l2)
{
printf("match at %d\n", i-l2);
j = 0;i = i-l2+1 ;
}
}
if(j == l2)
return i-l2;
else
return -1;
}
int main()
{
char *str="CCCC";
char *pat = "CC";
int index = -1;
index = pm(str, pat);
printf("%d", index);
return 0;
}
(Continued on next question...)
Other Interview Questions
| 