import string


class Node:
	def __init__(self):
		self._links = {}
		self._is_finite = False

	def set_link(self, letter, node):
		if letter == '.':
			for l in string.lowercase[:26]:
				self.set_link(l, node)
		if self._links.get(letter) is None:
			self._links[letter] = [node]
		else:
			self._links[letter].append(node)

	def get_links(self, letter):		
		return self._links.get(letter)

	def set_loop(self, letter):
		self.set_link(letter, self)

	def set_finite(self):
		self._is_finite = True

	def is_finite(self):
		return self._is_finite

	def  __repr__(self):
		return "FSM Node (_links = %s, _is_finite = %s)" % (self._links, self._is_finite)

class Automata:
	def __init__(self, pattern):
		self._root = Node()
		# parse pattern
		groups = []
		for char in pattern:
			if char == '*':
				n = len(groups)
				groups[n-1]['repeatale'] = True
			else:
				group = {
					'letter' : char,
					'repeatale' : False
				}
				groups.append(group)

		last = self._root
		# build FSM
		for group in groups:
			if group['repeatale'] == False:
				node = Node()
				last.set_link(group['letter'], node)
				last = node
			else:
				last.set_loop(group['letter'])
		last.set_finite()		
		print "FSM is build"


	def match(self, str):
		positions = [self._root]
		chars_count = len(str)
		for char_index, char in enumerate(str):
			next_positions = []
			for node in positions:
				nodes = node.get_links(char);
				if nodes is None:
					continue
				for node in nodes:
					if (char_index == chars_count -1 and node.is_finite()):
						return True
					next_positions.append(node)
			positions = next_positions
		return False

class Solution:
    # @param {string} s
    # @param {string} p
    # @return {boolean}
    def isMatch(self, s, p):
     	automata = Automata(p)
     	return automata.match(s)

def test():
	sol = Solution()
	assert sol.isMatch("abba", "ab*a") == True
	assert sol.isMatch("aa","a") == False
	assert sol.isMatch("aa","aa") == True
	assert sol.isMatch("aaa","aa") ==  False
	assert sol.isMatch("aa", "a*") ==  True
	assert sol.isMatch("aa", ".*") == True
	assert sol.isMatch("ab", ".*") == True
	assert sol.isMatch("aab", "c*a*b") == True

test()