Adobe Interview Question
Testing / Quality AssurancesYes,
For A contains B, let me give you an example:
A = "abcde" and
B = "bcd"
that we call "contains."
You can also say that B is a substring of A.
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<list>
#include<stack>
#include<utility>
#include<numeric>
#include<map>
#include<cctype>
#include<cstring>
#include<ctime>
#include<stdio.h>
//#define maxline 1000
using namespace std;
//void kmp(int a[],int b[]);
int kmp_search(char a[],char b[],int c[]);
int main()
{
char s[1000],w[1000];
int t[1000];
int i,j,k;
cin>>s;
cin>>w;
int cnd=0,pos=2;
t[0]=-1;
t[1]=0;
int leng=strlen(w);
while(pos<=leng){
if(s[pos-1]==s[cnd]){
cnd+=1;
t[pos]=cnd;
pos+=1;
}else if(cnd > 0){
cnd=t[cnd];
}else{
t[pos]=0;
pos+=1;
}
}
int l = kmp_search(s,w,t);
cout<<l<<endl;
}
int kmp_search(char s[],char w[],int ta[])
{
int m=0,i=0;
int len=strlen(s);
while((i+m)<=len){
if(w[i]==s[i+m]){
i++;
if(i==len){
return m;
}
}else{
m=m+i-ta[i];
if(ta[i]>-1){
i=ta[i];
}else{
i=0;
}
}
}
return m;
}
<pre lang="" line="1" title="CodeMonkey10162" class="run-this">#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<list>
#include<stack>
#include<utility>
#include<numeric>
#include<map>
#include<cctype>
#include<cstring>
#include<ctime>
#include<stdio.h>
//#define maxline 1000
using namespace std;
//void kmp(int a[],int b[]);
int kmp_search(char a[],char b[],int c[]);
int main()
{
char s[1000],w[1000];
int t[1000];
int i,j,k;
cin>>s;
cin>>w;
int cnd=0,pos=2;
t[0]=-1;
t[1]=0;
int leng=strlen(w);
while(pos<=leng){
if(s[pos-1]==s[cnd]){
cnd+=1;
t[pos]=cnd;
pos+=1;
}else if(cnd > 0){
cnd=t[cnd];
}else{
t[pos]=0;
pos+=1;
}
}
int l = kmp_search(s,w,t);
cout<<l<<endl;
}
int kmp_search(char s[],char w[],int ta[])
{
int m=0,i=0;
int len=strlen(s);
while((i+m)<=len){
if(w[i]==s[i+m]){
i++;
if(i==len){
return m;
}
}else{
m=m+i-ta[i];
if(ta[i]>-1){
i=ta[i];
}else{
i=0;
}
}
}
return m;
}
</pre><pre title="CodeMonkey10162" input="yes">
</pre>
Kindly specify what do you mean by A contains B. Does that mean substring of A or in any order ? (like in "pothole" contains "pole")
- jeangrey May 24, 2011