CareerCup

considering we allow pattern string like a*b, a.*b., etc,
character '.' means matching any character once, a star ('*') means matching previous character 0 ~ infinite times. (a* means matching '','a','aa','aaa',...; and .* means matching any string, including empty string)

we can solve this problem using dp:
1) parse pattern: pattern string 'ab*c' parsed to {{'a',false},{'b',true},{'c',false}}, the second bool value in each pair indicates whether the corresponding character is followed by a star ('*')
1) consider matching string of length m with parsed pattern of length n, we use f(i, j) to denote the matching result of string.substr(i) and pattern subsequence starting at j. f(i,j)=1 means a match while f(i,j)=0 means mismatch
2) we have the base case f(m,n) = true, since empty string matches empty pattern sequence.
3) for all 0 =< i < m, we have f(i,n) = false, since non-empty string will always mismatches empty pattern
4) for all 0=< j < n, we have f(m, j) = true if and only if pattern[j] to pattern[n-1] are all with stars.
5) for other cases, we can match from the end to head, we have: f(i, j) =
a) pattern[j] is with star:
a1) if pattern[j]=='.' || pattern[j]==str[i]: f(i,j) = f(i,j+1) || f(i+1,j+1) //we ignore current pattern character or use it to match current character in string
a2) otherwise, f(i,j) = f(i,j+1) //we can only ignore current pattern character to get a match
b) pattern[j] is without star:
b1) if pattern[j]=='.' || pattern[j]==str[i]: f(i,j) = f(i+1,j+1)
b2) otherwise f(i,j) = false
6) for all 0=< i < m, if f(i, 0) = true, it means substring starting from position i and ending at the tail of the string matches the whole pattern
7) previous steps will find occurances of matching substrings ending with the end of given string

8)since we want to find all occurances (ending at all possible positions), we simply match string.substr(0, len) with the whole pattern, for all 0 < len <= string.length().

9) time complexity O((m^2) *n), space complexity O(m*n)

Answer:
abbbacctlkjlkcccaaab
abbbacctlkjlkcccaaabb
abbbacctlkjlkcccaaabbb

I think it is not possible to implement it in a 45 minutes interview.
Maybe you only need to provide an idea as Murali Mohan answered.

Answer:
abbbacctlkjlkcccaaab
abbbacctlkjlkcccaaabb
abbbacctlkjlkcccaaabbb

I think it is not possible to implement it in a 45 minutes interview.
Maybe you only need to provide an idea as Murali Mohan answered.

I did spend some time about putting idea of DFA/NDFA to use but couldn't materialize in reasonable time.

Key idea that I used is -
Init =>
=====
Treat different parts of pattern as small(sub)Strings

For one match =>
===========
Fix (i)th subString into InputString and then go on to fix for all remaining subString(s) into remaining of InputString

Terminating conditions =>
===================
if we'r matching last subString => print the Match (we know position of all subStrings)

To find all matches =>
Find-next-Match of (i)th string and call match for remaining of InputString

Below is the pseudo-code I used :

Init //; this will put all patterns in an array/vector gsubString - in our example of size 3 gSubStrigns[]= {ab, c, b}

FindMatches(int subStringNo, string stringToMatch)
 {
	currPos = 0;
	currSubString = gSubStrings[subStringNo]
	while(currPos = FindNextMatch(currSubString, stringToMatch, currPos)	
	{
		if(subStringNo == gSubStrings.size - 1) 
		{
			PrintMatchedPattern;
		}else 
		{
			FindMatches(subString + 1, stringToMatch + currPos + currSubString.len ) // Match rest of the patterns in remaining string
		}
		curPos++		
	}
}

One performance enhancement that is left out is, when we know rest of sub-strings won't be able to match, due to length considerations, we don't call Find_Next_Match. Please note, when we say length - its not just sum of rest of substrings, we have to take pattern structure in consideration.

To find patterns using regular expressions, one needs to be build an NFA and it's equivalent DFA.

am not sure if this is correct. But you can get the count using regex pattern matching.

public static int getCount(String input, String regex) {
		int count = 0;
		Pattern pattern = Pattern.compile(regex);
		Matcher matcher = pattern.matcher(input);
		while(matcher.find()) {
			System.out.println(matcher.group());
			count++;
		}
		
		return count;
	}

Correct me if I m wrong.