CareerCup

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.

bool mainfunc(char *t, int tlen, char *p, int plen)
{
    return f(t, 0, tlen-1, p, 0, plen-1);  
}

// recursion function
bool f(char *t, int tst, int tend, char *p, int pst, int pend)
{
    if(tst>tend || pst>pend)
       return false; 

    int ti, pi; //ti:index of t; pi:index of p
    ti=tst;
    pi=pst;

    bool foundStar = false; // differentiate match chars w/wo *

    while(ti<=tend && pi<=pend)
    {
       while(p[pi]=='*')
       {
          pi++;
          foundStar=true;
       }

       if(pi>pend)
          return true; // the last char is * in pattern

       if(foundStar)
       {
          // match with each occurrence of p[next], return if anyone is true
          for(int i=ti;i<=tend;++i)
          {
              if(t[i]==p[pi] && f(t,i+1,tend,p,pi+1,pend)==true)
              {
                    return true;
              }
          }

          return false; //none of them return true.
       }
       
       if(t[ti]!=p[pi])
          return false;

       ti++;
       pi++;
    }
       
    if(ti<=tend || pi<=pend)
       return false;

    return true;
}

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;
}

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;

}

Please correct me if I was wrong:
it is true that an input string matches the given pattern once satisfying:
1) pattern length equals with input string's length;
2) fixed characters in pattern match the ones in the same positions of input string

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;
    }
}

kmp pattern matching algorithm can be used