dfa

gistfile1.rb

class Node
	attr_accessor :id, :type, :goto
	def initialize(type = nil, goto = {})
   		@type, @goto = type, goto
  	end	
	
end


def matches?(pattern, text)
	first = Node.new
	node = first
	i = 0
	pattern.each_char do |char|
		nextnode = Node.new
		endnode = Node.new
		endnode.type = 'end'
		node.id = i
		if char == '*'
			node.goto[char] = node
		else
			node.goto[char] = nextnode
		end
		if i==0
			node.type = 'start'
		elsif i==pattern.length-1
			
			if char == '*'
				node.type = 'end'
			else
				node.goto[char] = endnode
			end

		else
			node.type = 'transition'
		end
		if char != '*'
			node = nextnode
		end
		i+=1
	end

	i = 0
	currentstate = first
	text.each_char do |char| 
		currentstate = (currentstate.goto[char] or currentstate.goto['*']) # handle undefined GOTOs 
		if currentstate and i == text.length-1 and currentstate.type=='end'
			return true
		end
		i+=1
	end
	return false
	
end

puts matches?('a**********a', 'aa')