4 String matching with gaps In string matching with gaps the pattern P can contain a...

Transcribed Image Text:

4 String matching with gaps In string matching with gaps the pattern P can contain a gap character * that can match any string (of arbitrary length even length zero). An example of such a string is P= ab* ac * a, which occurs in the text T = bababacbcca in two ways: T: b ab ab ас bcc a P: ab * a ас or T: bab ab ac bcc a P: ab ас * a There are no gap characters in the text-only in the pattern. Solve the following exercises. 4.1 Show how to build a finite automaton that can find an occurrence of a gapped pattern in P in a text T in O(n) matching time. 4.2 Give an algorithm to find an occurrence of a pattern P containing gap characters in a text T in time O(n+m). That is, preprocessing time + matching time should be O(n+m)). 4 String matching with gaps In string matching with gaps the pattern P can contain a gap character * that can match any string (of arbitrary length even length zero). An example of such a string is P= ab* ac * a, which occurs in the text T = bababacbcca in two ways: T: b ab ab ас bcc a P: ab * a ас or T: bab ab ac bcc a P: ab ас * a There are no gap characters in the text-only in the pattern. Solve the following exercises. 4.1 Show how to build a finite automaton that can find an occurrence of a gapped pattern in P in a text T in O(n) matching time. 4.2 Give an algorithm to find an occurrence of a pattern P containing gap characters in a text T in time O(n+m). That is, preprocessing time + matching time should be O(n+m)).

Answer rating: 100% (QA)

set string input S a b c m7 for each automation Si S construct factor auto... View the full answer