@all: how is the problem solved using a heap...can someone explain. did not understand what was on the net...
On Thu, Feb 3, 2011 at 2:23 AM, Avik Mitra <tutai...@gmail.com> wrote: > I am proposing a solution for problem 2.. > >2. > > Given a text file, implement a solution to find out if a pattern > > similar to wild cards can be detected. > > fort example find if a*b*cd*, or *win or *def* exists in the text. > > Whatever be the pattern sort it must be regular expression. So in > principle, there always exists a deterministic finite automata with > exactly one finite state to accept the pattern. > Thus, the problem can be solved. For example take the case for > a*b*cd*. The automaton can can written as: > > 1.Set state=1. > 2. Scan the string until end of string is reached. > 2.1. If state is 1 and the letter is a then do not change the > state. > If the state is 1 and the letter is b then go to state 2. > if the state is 1 and the letter is c then go to state 3. > if the state is 1 and the letter is d then go to state 4. > > if the state is 2 and letter is a then go to state 4. > if the state is 2 and the letter is b then do not change > the state. > if the state is 2 and the letter is c the go to state 3. > if the state is 2 and the letter is d then go to state 4. > > if the state is 3 and the letter is a,b or c then go to > state 4. > if the state is 3 and the letter is d then do not change > state. > > if the state is 4 then do not change state. > > 3. If the state is 3 output "accept" else output "reject". > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- "People often say that motivation doesn't last. Well, neither does bathing - that's why we recommend it daily." -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
