15,901,035 members
See more:
Suppose we allow the pattern P to contain occurrences of a gap character ◊ that can match an arbitrary string of characters (even one of zero length). For example, the pattern ab◊ba◊c occurs in the text cabccbacbacab
Note that the gap character may occur an arbitrary number of times in the pattern but not at all in the text. Give a polynomial-time algorithm to determine whether such a pattern P occurs in a given text T, and analyze the running time of your algorithm.

I have googled but didnt find an answer. I only need to understand psuedocode.
I do have some idea that the pattern can be first converted into a regular expression then an NFA can be made which then need to be converted to a DFA...but I am not sure if this is the right approach?
Posted
Updated 24-Apr-15 2:04am
v3

## Solution 1

"I do have some idea that the pattern can be first converted into a regular expression then an NFA can be made which then need to be converted to a DFA...but I am not sure if this is the right approach?"

No - that's not an algorithm, which is what your tutor is looking for.
He hasn't asked for an implementation, he's looking for the underlying way that the task needs to be done, and an analysis of how well it works.

And we aren't going to do that for you!
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.

Try it yourself, you may find it is not as difficult as you think.