CareerCup

#include<iostream>
#include<cstring>

using namespace std;
int main()
{
    string pat = "";
    bool match = false;
    int j = 0;
    cout<<"Enter the pattern: ";
    cin >> pat;
    
    string str = "";
    cout<<"Enter the string: ";
    cin >> str;
    
    for(int i=0;str[i] != '\0';i++)
    {
        for(j=0;pat[j] !='\0';j++)
        {
            if(str[i] == pat[j] || pat[j] == '.')
            {
                if(str[i+1] == '\0')
                {
                    i++;
                    j++;
                    break;
                }
                i++;                
                continue;
            }
            else
            {
                if( pat[j] == '*')
                {
                    while(str[i] != pat[j+1] && str[i] != '\0')
                    {
                        if(pat[j+1] == '*' || pat[j+1] == '.')
                        {
                            j++;
                            if(pat[j+1] == '.')
                            {
                                i++;
                            }
                        }
                        else
                        {
                            i++;
                        }
                    }
                    if(str[i] == '\0' && pat[j+1] != '\0')
                    {
                        break;
                    }
                    else
                    {
                        //i++;
                    }                     
                }
                else
                {                   
                    break;
                }
            }
        }
        if(pat[j] == '\0')
        {
            cout<<"Matched substring: "<<str.substr(0,i)<<endl;
            match = true;
            break;
        }
    }
    if(match == false)
    {
        cout<<"No matched substring\n";
    }
}

bool
charMatch(char s, char p) {
  if (s == p || p == '.' || p == '*') return true;
  return false;
}

bool
patternMatchHelper(const string& s, int sPos, const string& pattern, int pPos) {
  int sSz = s.size(), pSz = pattern.size();
  if (sPos == sSz - 1 && pPos == pSz - 1) return true;
  if (sPos >= sSz || pPos >= pSz) return false;
  char sCh = s[sPos + 1], pCh = pattern[pPos + 1];
  if (pCh == '*') {
    // '*' representing 0 char
    if (patternMatchHelper(s, sPos, pattern, pPos + 1)) return true;
    // '*' representing > 1 char
    if (patternMatchHelper(s, sPos + 1, pattern, pPos)) return true;
  }
  if (charMatch(sCh, pCh)) { // '*' representing 1 char
    if (patternMatchHelper(s, sPos + 1, pattern, pPos + 1)) return true;
  }
  return false;
}

bool
patternMatch(const string& s, const string& pattern) {
  return patternMatchHelper(s, -1, pattern, -1);
}

int
main(int argc, char** argv) {
  cout << "string vs pattern test:" << endl;
  if (argc == 3) {
    cout << argv[1] << " vs " << argv[2] << " : "
        << patternMatch(argv[1], argv[2]) << endl;
  }
}

Simple iterative matcher, worst case O(m x n)

int match(const char* text, const char* pattern) {
  if (!pattern || !text) {
    return false;
  }
  
  // Iterate over all sub-strings in the string of the form                       
  // text[0..n], text[1..n], text[2..n], ... , text[n..n]                         
  const char* textItr = text;
  while (*textItr) {
    const char *patternItr = pattern;
    bool match = true;
    
    // Match the pattern against the current string in question.                  
    while (*textItr && *patternItr) {
      // The current character in the pattern                                     
      const char current = *patternItr;
      // The lookahead character (for the kleene operator)                        
      const char lookahead = *(patternItr + 1);
      
      if (lookahead == '*') {
        // This is a greedy operator                                              
        while (textItr && (current=='.' || current==*textItr)) {
          ++textItr;
        }
        patternItr += 2; // Skip forward two steps past '*'                       
      } else {
        if (current == '.') {
          textItr++;
          patternItr++;
        } else if (current == *textItr) {
          textItr++;
          patternItr++;
        } else {
          match = false;
          break;
        }
      }
    }
    
    // Need the latter part of the conditional                                    
    // to make sure we've matched the whole pattern                               
    if (match && !(*patternItr)) {
      return true;
    }
    
    ++textItr;
  }
  
  return false;
}

using kmp algorithmn

Questions is a bit underspecified. Assuming you can have arbitrarily many pattern special chars in there and then it gets complicated. All solutions except the downvoted one (LOL) would fail on that.

I could even write this in an ediotr and it COMPILED and worked out of the box. This is awesome :D.

#include <iostream>
#include <string>

class FindPattern
{
private:

	bool parse(
		std::string::const_iterator frontier, 
		std::string::const_iterator frontierEnd, 
		std::string::const_iterator pattern,
		std::string::const_iterator patternEnd,
		std::string& outResult)
	{
		if(pattern == patternEnd)
		{
			outResult = "";
			return true;
		}
		
		if(frontier == frontierEnd)
			return false;
		
		switch(*pattern)
		{
			case '*': 
			{
				for(auto fit = frontier; fit != frontierEnd; fit++)
				{
					if(parse(fit, frontierEnd, pattern + 1, patternEnd, outResult))
					{
						outResult = std::string(frontier, fit) + outResult;
						return true;
					}
				}
				
				return false;
			}break;
			
			default: 
			{
				if((*frontier == *pattern) || (*pattern == '.'))
				{
					if(!parse(frontier + 1, frontierEnd, pattern + 1, patternEnd, outResult))
						return false;
					
					outResult = *frontier + outResult;
					return true;
				}
				else
					return false;
			}
		}
	}
	
public:
	std::string operator()(std::string frontier, std::string pattern)
	{
		std::string res;
		for(auto fit = frontier.begin(); fit != frontier.end(); fit++)
		{
			if(parse(fit, frontier.end(), pattern.begin(), pattern.end(), res))
				return res;
		}
		return ">>FAILED<<";
	}
};


int main(int argc, char** argv)
{
	if(argc == 3)
		std::cout << "Found: \"" << FindPattern()(argv[1], argv[2]) << "\"" << std::endl;
	else
		std::cout << "Invalid usage! Need two parameters..." << std::endl;
		
	return 0;
}

public static String matcher(String val, String pattern)
    {
	StringBuffer sbuffer = new StringBuffer(val.length());
	
	int i = 0;
	int j = 0;

	while (i < val.length() && j < pattern.length())
	{
	    char v = val.charAt(i);
	    char p = pattern.charAt(j);

	    if (v == p)
	    {
		sbuffer.append(v);
		i++;
		j++;
		
		continue;
	    }
	    
	    if (p == '*')
	    {
		j++;
		if (j == pattern.length())
		{
		    sbuffer.append(val.substring(i));
		    return sbuffer.toString();
		}

		p = pattern.charAt(j);
		
		while (v != p)
		{
		    sbuffer.append(v);
		    i++;
		    v = val.charAt(i);
		}

		continue;
	    }		

	    if (p == '.')
	    {
		sbuffer.append(v);

		j++;
		i++;
		continue;
	    }
	    
	    sbuffer = new StringBuffer(val.length());
	    i++;
	    j=0;
	}
	return sbuffer.toString();
    }

int matcher_recurse(char text[], int i, char pattern[], int j) {
  // If at end of pattern, we have found a match
  if(pattern[j] == '\0') return 1;
  // If not at end of pattern but at end of text,
  // we have not found a match.
  if(text[i] == '\0') return 0;
  // Try to match any character
  if(pattern[j] == '.') return matcher_recurse(text, i+1, pattern, j+1);
  // Trying to match one or more characters
  // Caveat: This isn't greedy. It tries to use minimum number
  // of matching characters.
  if(pattern[j] == '*') {
    int k = 0;
    int ret;
    while(text[i+k] == pattern[j-1]) {
      ret = matcher_recurse(text, i+k+1, pattern, j+1);
      if(ret == 1) return 1;
      k++;
    }
    return matcher_recurse(text, i, pattern, j+1);
  }
  // Finally, normal text match
  if(text[i] == pattern[j]) {
    return matcher_recurse(text, i+1, pattern, j+1);
  }
  return 0;
}

int matcher(char text[], char pattern[]) {
  return matcher_recurse(text, 0, pattern, 0);
}