Facebook Interview Question
Software Engineer / DevelopersCountry: United States
here is the code. It checks if the second string is a pattern in a first string. for instance try:
./a.out "This is the string " "is*is"
./a.out "This is the string d " "*is*is*dd"
./a.out "This is the string dd " "*is*is*dd"
./a.out "This is the string dd " "*is*is*dd**k"
the code:
#include <iostream>
using namespace std;
bool checkPattern(char *input, char *pattern) {
int inputIndex=0;
int patternIndex=0;
while(input[inputIndex] != '\0') {
if(pattern[patternIndex] == '\0') return true;
else if(pattern[patternIndex] == '*') patternIndex++;
else if(pattern[patternIndex] == input[inputIndex] ) {inputIndex++; patternIndex++;}
else if(pattern[patternIndex] != input[inputIndex] ) inputIndex++;
}
return false;
};
main(int argc,char * argv[])
{
cout << "string: \'" << argv[1] << "\'" << endl << "pattern: \'" << argv[2] << "\'" << endl;
checkPattern(argv[1],argv[2]) ? cout << "yay" : cout << "nay";
cout << endl;
}
I don't think the code is correct:
"This is the string " "is*is" should not be a match, but your program returned "yay"
Moreover, whether inputIndex can keep increasing definitely depends on whether the previous pattern character is a wildcard *
Also, I don't think you took care of the case when the pattern runs out but input still has characters left, which should not be a match, e.g., "xyzxyz" should not be a match for "*y*y"
use kmp as follows:
1. cut down the head and tail which is not '*' from the pattern, and match the head and tail with the text. If match, cut down the text head and tail and go on to 2; returns false otherwise.
for example, text: abcdadabaccdba, pattern: ab*dad*ba*dba, then head = 'ab' and tail = 'dba', both match the text head and tail correspondingly. so the new text would be 'cdadabacc' and new pattern '*dad*ba*'.
2. split the remaining pattern by * and build the kmp for each part, then use them to match the text one by one.
in the above case, '*dad' matches 'cdad', then '*ba' matches 'aba', the last '*' is for the tailing 'c'. done.
//Kmp algorithm with some modification works fine
#include<iostream>
#include<string>
using namespace std;
int array[100];
void precompute(string original,string matched)
{
int k=0;
array[0]=0;
for(int q=1;q<matched.length();q++)
{
while(k>0&&(matched[k+1-1]!=matched[q])&&matched[k+1-1]!='*')
{
k=array[k-1];
//cout<<k<<"hii"<<endl;
}
if(matched[k+1-1]==matched[q]||matched[k+1-1]=='*')
k=k+1;
array[q]=k;
// cout<<array[q]<<endl;
}
}
int main()
{
//Kmp-algorithm
string original,matched;
cin>>original;
cin>>matched;
int q=0;
precompute(original,matched);
for(int i=0;i<original.length();i++)
{
while(q>0&&(matched[q+1-1]!=original[i]&&matched[q+1-1]!='*'))
q=array[q-1];
if(matched[q+1-1]==original[i]||matched[q+1-1]=='*')
q=q+1;
if(q==matched.length())
{
cout<<i+2-matched.length()<<endl;
q=array[q-1];
}
}
system("pause");
return 0;
}
Try it out at: ideone.com/eG3sQ
bool Matches(const string& str, const string& pattern) {
int pos = 0;
int str_len = str.size();
int pattern_len = pattern.size();
bool saw_wildcard = false;
for (int i = 0; i < pattern_len; ++i) {
if (pattern[i] == '*') {
saw_wildcard = true;
continue;
}
if (saw_wildcard) {
while (pos < str_len && str[pos] != pattern[i])
pos++;
if (pos == str_len)
return false;
else
pos++;
} else {
if (str[pos] != pattern[i])
return false;
else
pos++;
}
saw_wildcard = false;
}
// if last char in pattern is not a wildcard, then extra char in the input should not match
if (!saw_wildcard && pos < str_len)
return false;
return true;
}
#include<iostream>
#include<string>
using namespace std;
struct node
{
char a;
node *l;
int flag;
}*start;
bool matchReg(node *q,int i);
string t,p;
int n,m;
int main()
{
start=NULL;
node *temp,*q;
cin>>t;
cin>>p;
n=t.length();
m=p.length();
int i;
i=0;
if(t[i]=='*')
i++;
while(i<n-1)
{
if(t[i+1]=='*' && t[i]!='*')
{
if(start==NULL)
{
start=new node;
start->a=t[i];
start->l=NULL;
start->flag=1;
temp=start;
}
else
{
q=new node;
q->a=t[i];
q->l=NULL;
q->flag=1;
temp->l=q;
temp=q;
}
}
else if(t[i]!='*')
{
if(start==NULL)
{
start=new node;
start->a=t[i];
start->l=NULL;
start->flag=0;
temp=start;
}
else
{
q=new node;
q->a=t[i];
q->l=NULL;
q->flag=0;
temp->l=q;
temp=q;
}
}
i++;
}
if(t[i]!='*')
{
if(start==NULL)
{
start=new node;
start->a=t[i];
start->l=NULL;
start->flag=0;
temp=start;
}
else
{
q=new node;
q->a=t[i];
q->l=NULL;
q->flag=0;
temp->l=q;
temp=q;
}
}
if(matchReg(start,0))
cout<<"Accepted";
else
cout<<"Rejected";
}
bool matchReg(node *q,int i)
{
if(q==NULL && i==m)
return true;
else if(q==NULL && i!=m)
return false;
else if(q->l==NULL && q->flag==1 && i==m)
return true;
else if(q!=NULL && i==m)
return false;
else if(q->a!=p[i] && q->flag==0)
return false;
else if(q->a==p[i] && q->flag==0)
return matchReg(q->l,i+1);
else
{
bool b1=matchReg(q->l,i+1);
bool b2=matchReg(q,i+1);
bool b3=matchReg(q->l,i);
return (b1||b2||b3);
}
}
Another recursion using different function signature.
bool f(char* s, char* p)
{
if(*s=='\0' && *p=='\0')
return true;
if(*s=='\0' && *p=='*')
return f(s, p+1);
if(*s=='\0')
return false;
bool foundStar = false;
char* cur = p;
//handle multiple stars in a row.
while(*cur == '*')
{
cur++;
foundStar = true;
}
//if ending with *, return true.
if(*cur == '\0')
return true;
if(foundStar)
{
return f(s+1, cur-1) || f(s, cur) || f(s+1, cur);
}
else
{
if(*cur==*s)
return f(s+1, cur+1);
else
return false;
}
}
use recursion. When a * is found and it is not the ending char in the pattern, find each occurrence of the next non-* char of the pattern in the text, call recursion for the substring in the text starting from each occurrence. Return true if any of the recursion is true.
- jiangok2006 July 20, 2012