CareerCup

The 4th example shows incorrect output

Input:
090m90mm90mmm90mm90m909
0m*9
Output:
5

Output should be 21, not 5.

The problem is easy, if you can use regular expressions.
If you can't use regular expressions; this is rather difficult.

Unless the job description specifies 'Perl' or the job requires serious expertise in regular expressions... it's not the best choice for an interview question (imo).

[C#]

static int LongestSubstring(string masterString, string scanString)
        {
            string pattern = Regex.Replace(scanString, "\\*", "([A-Z]|[a-z]|[0-9])*");

            MatchCollection matches = Regex.Matches(masterString, pattern);
            int maxLength = 0;

            foreach (Match match in matches)
            {
                if (match.Length > maxLength)
                {
                    maxLength = match.Length;
                }
            }
            return maxLength;
        }

the problem seems very difficult for me.
it is very confusing for me.
is there any one who understand the problem??

public static int findSubStringMaxLength(String master, String scan)
    {
        int currLen = 0, maxLen = 0;
        char charBeforeStar = '~';// ~ is just a falg to indicate we are out of the * mode
        int i = 0, j = 0, k = 0;
        int masterLen = master.length();
        int scanLength = scan.length();
        // We need to search starting from each index of master, this is to find the max length match.
        for (k = 0; k < masterLen; ++k)
        {
            // Loop on the scan and try to match from master starting from index k
            charBeforeStar = '~';
            currLen = 0;
            for (i = 0, j = k; i < scanLength; ++i)
            {
                if (j >= masterLen)// This means we hit the end of master but not yet done with the scan
                    break;
                // check if next char is '*' if yes increment pointer i by 2 and conitnue to search
                if (i < scanLength - 1)
                {
                    if (scan.charAt(i + 1) == '*')
                    {
                        charBeforeStar = scan.charAt(i);
                        i++;
                        continue;
                    }
                }
                // If it match increment both pointer i and j by one and also the length and 
                // change the flag for charBeforeStar back to ~, meaning we are
                // not in the star mode.
                if (scan.charAt(i) == '.' || scan.charAt(i) == master.charAt(j))
                {
                    ++j;
                    ++currLen;
                    if (i == scanLength - 1)// This means we found a match capture the length
                    {
                        if (currLen > maxLen)
                            maxLen = currLen;
                    }

                    if (charBeforeStar != '~' && i == scanLength - 1 && j < masterLen)//Match found but need to continue to find longer match
                        ;
                    else
                    {
                        charBeforeStar = '~';
                        continue;
                    }
                }
                // We are in starMode and we move in master but not in scan
                if (charBeforeStar != '~')
                {
                    if (charBeforeStar == '.' || charBeforeStar == master.charAt(j))
                    {
                        ++j;
                        ++currLen;
                        --i;// to make sure we dont move in scan String
                        continue;
                    } else
                        charBeforeStar = '~';
                }
                // we are here means the search has failed or not started yet.
                break;
            }// end of for loop
            if (currLen > maxLen && i == scanLength)
            {
                maxLen = currLen;
            }
            currLen = 0;
            if(masterLen-k<maxLen)
                break;
        }// outer for loop
        return maxLen;
    }

Since the master only has [A-Z][a-z][0-9], I am using Substitutions

#!/usr/bin/perl

use warnings;
use strict;

my @input = <STDIN>;
chomp @input;
word_match(@input);

sub word_match {

	$_ = shift;
	chomp;
	my $scan;
	if ( defined $_ ) {
		$scan = shift;
	}
		my $length = length($_);
		my $longest =0;
		
	if(/$scan/){
		while (/$scan/) {
			my $before = length($_);
	#		print "before: $_ ".length($_)."\n";
			s/$scan/*/;
	#		print "stared:$_ ".length($_)."\n";
			my  $after = length($_);
			if($before - $after>$longest-1){
			$longest = 	$before - $after+1;
	#		print "longest now :$longest\n"
			}
			s/\*/#/;
		}
		print "\n$longest\n";
	}
	else {
		print 0;
	}
}

Can anyone explain the test cases?...Thanks in advance.

import java.util.regex.Pattern;
import java.util.regex.Matcher;
import java.io.Console;

public class StringMatch {
static String masterStr,scanStr;
static int max;
public static void main(String[] args){
Console obj=System.console();
System.out.println("Enter Master Input String");
masterStr=obj.readLine();
System.out.println("Enter Scan Pattern String");
scanStr=obj.readLine();
check_pattern();
System.out.println("Maximum length of the pattern is \t"+max);
}
static void check_pattern (){
Pattern p = Pattern.compile(scanStr);
for (int i=0;i<masterStr.length() ;i++ )
{
scanStr=masterStr.substring(i);
Matcher m = p.matcher(scanStr);
if(m.find())
if(max<m.end()-m.start())
max=m.end()-m.start();
}
}
}

bool match(char* p,char* s,int len)
{
	switch(*p)
	{
		case '\0':
			printf("%d\t",len);
			return !*s;
		case '.':
			return *s && match(p+1,s+1,len);
		case '*':
			return match(p+1,s,len+1) ||(*s && match(p,s+1,len+1));
		default:
			return *s==*p && match(p+1,s+1,len+1);
	}	
}