Re: Question #4 Hwk#3

Shirley Browne (browne@cs.utk.edu)
Tue, 17 Oct 1995 09:43:56 -0400

>I'm a bit confused on #4 It says "Explain how to use the algorithm to
>report ALL matches of the regular expression in the form of a start
>position and a length."
>
>Length of what? Are we using a PAT tree similiar to #3 in which
>external nodes point to words? If so when we have external nodes that
>point back into the orignal text, do you mean you want the length of the
>word we are pointing to with an external node?

Dr. Berry already replied, but I'll reply too just to clarify further.
I mean report the length of the match to the regular expression.
For example, if the text string were

10001010001

and the regular expression were 1010*, then matches would be

position 5, length 3
position 5, length 4
position 5, length 5
position 5, length 6

BTW, external nodes in a PAT tree don't point to words, they
point to sistrings.

Dr. Browne