CareerCup

<pre lang="c++" line="1" title="CodeMonkey23602" class="run-this">bool is_match(const char * text, const char * pattern)
{
const char equal_char = '@';

size_t text_len = strlen(text);
if(!text_len)
throw std::invalid_argument("wrong text`s length");

size_t patt_len = strlen(pattern);
if(!patt_len)
throw std::invalid_argument("wrong pattern`s length");

if(strchr(pattern, '*') == NULL)
throw std::invalid_argument("pattern has no \"*\"");

char * compare_str;

if(text_len >= patt_len)
{
compare_str = new char[text_len];

if(pattern[0] == '*') {
int i = text_len - 1, j = patt_len - 1;
while(pattern[j] != '*')
compare_str[i--] = pattern[j--];

memset(compare_str, equal_char, i + 1);
}
else if (pattern[patt_len - 1] == '*') {
int i = 0;
while(pattern[i] != '*')
compare_str[i] = pattern[i++];

memset(compare_str + i, equal_char, text_len - i);
}
else {
int i = 0;
while(pattern[i] != '*')
compare_str[i] = pattern[i++];

int j = text_len - 1;
int k = patt_len - 1;
while(pattern[k] != '*')
compare_str[j--] = pattern[k--];

memset(compare_str + i, equal_char, j - i + 1);
}
}
else
{
int i = 0, j = 0;
compare_str = new char[patt_len];
while(pattern[i])
{
if(pattern[i] != '*')
compare_str[j++] = pattern[i];
++i;
}
}

for(int i = 0; i < text_len; ++i)
{
if(text[i] == compare_str[i] || compare_str[i] == equal_char)
continue;

delete[] compare_str;
return false;
}

delete[] compare_str;
return true;
}</pre><pre title="CodeMonkey23602" input="yes">
</pre>

int regexpr(char *r,char *str)
{
int flag = 1;
while(*r && *str)
{
if(*r != '?' && *r != '*')
{
if(*r == *str)
{
str++;
r++;
continue;
}
else
{
flag = 0;
return 0;
}
}
else if(*r == '?')
{
str++;
r++;
continue;
}
else if(*r == '*')
{
while(*r == '*' || *r == '?')
r++;
while(*str != *r)
str++;
continue;
}
}
if(*str != '\0' && *r != '\0')
return 0;
else
return 1;
}

bool is_match(char* text, char* pattern)
{
  assert(text && pattern);

  char* token = strtok(pattern, '*');

  while (token)
  {
    char* str = strstr(text, token);

    if (!str)
       return false;

    text += strlen(str);
    token = strtok(NULL, '*');
  }

  return true;
}

<pre lang="java" line="1" title="CodeMonkey30014" class="run-this">public static boolean is_match(String input, String pattern){
if(pattern=="*") return true;

int inputIndex=0;
int patternIndex = 0;

for(; inputIndex<input.length(); inputIndex++){
if(patternIndex==pattern.length()) break;
if(pattern.charAt(patternIndex)=='*'){
char nonStarChar = ' ';
while(++patternIndex<pattern.length()){
if(pattern.charAt(patternIndex)!='*'){
nonStarChar = pattern.charAt(patternIndex);
break;
}
}
if(nonStarChar==' ') return true;
while(inputIndex<input.length()){
if(input.charAt(inputIndex)==nonStarChar){
inputIndex--;
break;
}
inputIndex++;
}
if(inputIndex==input.length()) return false;
else continue;
}
else if(input.charAt(inputIndex)==pattern.charAt(patternIndex)){
patternIndex++;
continue;
}
else break;
}

if(inputIndex==input.length() && patternIndex==pattern.length()) return true;
return false;
}</pre><pre title="CodeMonkey30014" input="yes">
</pre>

modified bitap will do :) with difference k(possible errors) as (differences of strings length)+1(for symbol *)...hellooo and h*o has one of the k as 5 which is 7-3+1...Any ideas?

Use regualr expression would be more easier to solve this problem

public boolean isMatch(String s, String target) {
		target = target.replace("*", ".*");
		Pattern p = Pattern.compile(target);
		Matcher m = p.matcher(s);
		if (m.matches()) {
			return true;
		} else {
			return false;
		}
	}

i'm just trying to capture some very raw idea coming on the top of my head:
it likes a dynamic programming.hasToMatch() means from s.at(sStart) on, it has to fully match on partern from pStart
isMatch(string s, string partern,int sStart, int pStart)
{
if(sStart<0) return false;
if(partern.length==pStart)
return true;
if(partern.at(pStart) == "*")
return isMarth(s,partern, sStart, pStart+1)
else
{
int i=hasToMatch(s,partern, sStart,pStart);
return (isMatch(s,partern, sStart+i,pStart+i) || isMatch(s,partern,sStart+1,pStart))

}
}
int hasToMatch(string s, string partern, int sStart, int pStart)
{
int i=0;
while (partern.at(pStart+i)!="*")
{
if(partern.at(pStart+i) == s.at(sStart+1))
i++;
else return -sStart;
}
return i;
}

Do a recursion every time you encounter a '*'.

public static bool SearchWildCard(string text, string pattern, int textPosition, int patternPosition)
        {
            int i = 0;
            while (textPosition + i < text.Length && patternPosition + i < pattern.Length)
            {
                if (pattern[patternPosition + i] == '*')
                {
                    if (SearchWildCard(text, pattern, textPosition+i, patternPosition+i + 1))
                        return true;
                    else
                    {
                        textPosition++;
                        i = 0;
                    }
                }
                else
                {
                    if (text[textPosition + i] == pattern[patternPosition + i] || pattern[patternPosition + i] == '?')
                        i++;
                    else
                    {
                        textPosition++;
                        i = 0;
                    }
                }
            }

            if (patternPosition + i == pattern.Length)
                return true;
            else
                return false;
        }
    }

It's sadly to say that the recursion method fails on the following tests:
(The last parameter is what value should method return.)

TestIsMatch("", "*", true); //
TestIsMatch("", "**", true); //
TestIsMatch(" ", " *", true);//
TestIsMatch("a", "", false);//
TestIsMatch("asdasdasdabc abc", "abc*abc", false);//
TestIsMatch("asdasdasdabc abc", " *abc", false);//
TestIsMatch("asdasdasdabc abcasd", "abc*abc", false);//

Just tested this for several inputs like H*l*o, H*, H*l*l*, H*l*l*o and they all seem to work:

/// <summary>
        /// Removes the char.
        /// </summary>
        /// <param name="str">The STR.</param>
        /// <param name="i">The i.</param>
        /// <returns></returns>
        private string RemoveChar(string str, int i)
        {
            if (str == null)
            {
                return null;
            }

            if (str.Length == 0)
            {
                return string.Empty;
            }

            StringBuilder builder = new StringBuilder(str.Length - 1);

            for (int j = 0; j < str.Length; j++)
            {
                if (i != j)
                {
                    builder.Append(str[j]);
                }
            }

            return builder.ToString();
        }

/// <summary>
        /// Matches the pattern
        /// </summary>
        /// <param name="text">The text.</param>
        /// <param name="pattern">The pattern.</param>
        /// <returns>True if pattern is matched, False otherwise</returns>
        private bool PatternMatch(string text, string pattern)
        {
            if ((text == null) || (pattern == null))
            {
                return false;
            }

            if (text.Length == 0)
            {
                return ((pattern.Length == 0) || ((pattern.Length == 1) && (pattern[0] == '*')));
            }

            // Since we checked for text.Length to be 0 above
            // If we hit pattern.Length 0 then pattern does not match
            if (pattern.Length == 0)
            {
                return false;
            }

            string newPattern = RemoveChar(pattern, 0);

            if (pattern[0] != '*')
            {
                return (text[0] == pattern[0]) && (PatternMatch(RemoveChar(text, 0), newPattern));
            }                       

            // No characters matched with *
            if (PatternMatch(text, newPattern))
            {
                return true;
            }

            for (int i = 0; i < text.Length; i++)
            {
                string nonStarredString = text.Substring(i + 1);
                    
                if (PatternMatch(nonStarredString, newPattern))
                {
                    return true;
                }
            }            

            return false;
        }

        /// <summary>
        /// Pattern can contain any characters + '*' character which means zero or more characters. 
        /// For example: is_match("hello", "h*o") returns true; is_match("hello", "hel*lo") also returns true.
        /// </summary>
        [TestMethod]
        public void PatternMatch()
        {
            string text = "Hello";
            string pattern = "H*l*l*o";

            Assert.IsTrue(PatternMatch(text, pattern));
        }

bool Tokenizer::searchPattern(char *str, char *pat) {
    int i=0, j=0;
    
    int firstToken = parseToken(str,pat,&i,&j,'*'); // Get the first token and try to match the pattern

    if(firstToken==-1) return false; // If no such first pattern, return false
    
    if(pat[j]==NULL) return true; // If we reached end of the pattern, return true
    
    int secondToken = parseToken(str,pat,&i,&j,NULL); // Get the second token after the '*'

    if(secondToken==-1) return false; // If no such second pattern, return false
    
    return true; // Yay! Found it.
}

int Tokenizer::parseToken(char *str, char *pat, int *i, int *j, char stopChar) {
    int k = *j;
    
    while(str[*i]!=NULL && pat[k]!=NULL)
    {
        if(str[(*i)++]==pat[k])
            k++;
        else
            k=*j;
                
        if(pat[k]==stopChar)
        {
            *j = k + 1;
            return *i;
        }
    }
        
    return -1;
}

bool isMatch(char *text,char *pattern){
if (text == NULL || pattern == NULL)
return false;

if (*pattern == '\0')
return *text == '\0';

if (*pattern != '*')
return (*pattern==*text) && isMatch(text+1,pattern+1);
else{
return (isMatch(text,pattern+1)) ||
((*text != '\0') && isMatch(text+1,pattern));
}
}

#include <iostream>
//You can write validate pattern function.

bool compareWithPattern(const char* input, const char* pattern)
{
while(*pattern != '\0')
{
if(*pattern == '*')
{
pattern++;

while(*pattern != *input)
{
if (*input == '\0')
{
return false;
}
else
{
input++;
}
}
}

if(*pattern != *input)
return false;

++pattern;
++input;
}

return true;
}

bool findPattern(const char* input, const char* pattern)
{
bool found = false;
while(*input != '\0')
{
if (*input == *pattern)
{
found = compareWithPattern(input,pattern);
input++;
if(found)
break;

}
else
{
input++;
}
}
return found;
}



int main()
{
char* input = "I am great, nil is ueless";
char* pattern = "s*s";
bool result = findPattern(input, pattern);
std::cout<<result;

}

<pre lang="" line="1" title="CodeMonkey14249" class="run-this">void PatternMatching(char*& word, char*& pattern)
{
int i = 0;
int j;
int len_word = strlen(word);
int len_pattern = strlen(pattern);
int num_words;
while(pattern[i] != '*')
{
if(word[i] == pattern[i])
{
i++;
}
else
{
break;
}
}
num_words = len_pattern - i - 1;
for(j = 0; j< num_words; j++)
{
if(pattern[len_pattern - 1] == word[len_word - 1])
{
len_pattern--;
len_word--;
}
else
{
break;
}
}
if(i + j + 1 == strlen(pattern))
{
printf("Pattern matched \n");
}
else
{
printf("unmatched pattern \n");
}
}
</pre><pre title="CodeMonkey14249" input="yes">
</pre>

class Program
    {
        static void Main(string[] args)
        {
            string text = "Hello";
            string patten = "Hello";
            Console.WriteLine(text + ":" + patten + isMatch(text,patten));
            patten = "H*";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));
            patten = "M*";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));
            patten = "*o";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));
            text = "hell";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));
            patten = "H*o";
            text = "Hello";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));
            patten = "H?*o";
            text = "Hello";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));

            patten = "H?*lo";
            text = "Helko";
            Console.WriteLine(text + ":" + patten + isMatch(text, patten));
            Console.Read();

        }

        static bool isMatch(string text, string pattern)
        {
            if (pattern.Length == 0) return false;
            if (text.Length == 0) return false;
            // pattren has "*","?"

            int textStartIndex = 0;
            int textEndIndex = text.Length - 1;
            int PatternStartIndex = 0;
            int PatternEndIndex = pattern.Length - 1;

            while (PatternStartIndex < PatternEndIndex)
            {
              switch (pattern[PatternStartIndex])
              {
                  case '*':
                      while(PatternEndIndex > PatternStartIndex )
                      {
                         if (pattern[PatternEndIndex] != text[textEndIndex])
                          {
                            return false;
                          }
                          PatternEndIndex --; textEndIndex --;
                      }

                      break;
                  case '?':
                      PatternStartIndex ++;
                      textStartIndex ++;
                      break;
                  default:
                      if (pattern[PatternStartIndex] != text[textStartIndex])
                      {

                        return false;
                      }
                       PatternStartIndex++; textStartIndex ++;
                      break;

              }
            
            }
          
            return true;
        }

#include<iostream>
using namespace std;
bool isMatch(const char *s,const char *p);
int main()
{
char *s="hello";
char *p="";
if(isMatch(s,p))
cout<<"match";
else
cout<<"no match";
}
bool isMatch(const char *s, const char *p) {
if(*p == '\0')
return (*s == '\0');
if(*p!='*')
return (*p==*s && isMatch(s+1,p+1));
while(*s!='\0')
{
if(isMatch(s,p+1))
return true;
s++;
}
return isMatch(s,p+1);
}

#include<iostream>
using namespace std;
bool isMatch(const char *s,const char *p);
int main()
{
char *s="hello";
char *p="hel*o";
if(isMatch(s,p))
cout<<"match";
else
cout<<"no match";
}
bool isMatch(const char *s, const char *p) {
if(*p == '\0')
return (*s == '\0');
if(*p!='*')
return (*p==*s && isMatch(s+1,p+1));
while(*s!='\0')
{
if(isMatch(s,p+1))
return true;
s++;
}
return isMatch(s,p+1);
}

IMHO - Most people will not have time to go through code. A neatly explained algorithm works the best.
As for this question. This is my suggestion
1) Divide the pattern into 2 parts so that first part doesn't have a '*'. e.g. Divide "ab*bc*cd" into "ab" and "bc*cd"
2) Using KMP find first occurrence of "ab". For the rest of string, recursively search for the pattern "bc*cd". If match is found return true.
3) Repeat for remaining occurrence of "ab".
4) Return false if not more instance of "ab" lest.