Analysis of Algorithms : An Active Learning Approach

5.1 STRING MATCHING 123 In the first case we are done, but in the second, we move the starting point in the text by one characte ...

124 MATCHING ALGORITHMS if (subLoc > length(substring)) return textStart // found a match else return 0 // indicates no match ...

5.1 STRING MATCHING 125 form of the word “automata”) is a simple machine that has a current state and a transition function. The ...

126 MATCHING ALGORITHMS Each success link of a Knuth-Morris-Pratt automaton causes the “fetch” of a new character from the text. ...

5.1 STRING MATCHING 127 the substring, we know that the first four characters matched, and so the “ab” that matched substring ch ...

128 MATCHING ALGORITHMS be no more than S
2 mismatched character comparisons. This means a total of 2S
3 matched (fact 1) and ...

5.1 STRING MATCHING 129 time because the h does appear in the pattern, we move the pattern only two characters to the right so t ...

130 MATCHING ALGORITHMS appears “closer” to the front than the repetition of the end characters of the pattern. If the jump arra ...

5.1 STRING MATCHING 131 character of the pattern as shown in Fig. 5.6(b). Then we begin the matching process from the right end ...

132 MATCHING ALGORITHMS If you trace this algorithm with the pattern “datadata,” you will find that slide[d] = 3,slide[a] = 0, a ...

5.1 STRING MATCHING 133 to add 7, 8, or 9, respectively. Thinking about this in general shows the amount we add for a mismatch o ...

134 MATCHING ALGORITHMS test = test - 1 target = target - 1 end while for i = 1 to target do jump[ i ] = MINIMUM( jump[ i ], len ...

5.1 STRING MATCHING 135 Analysis In the following analysis, we will use P to represent the number of characters in the pattern, ...

136 MATCHING ALGORITHMS Calculate the slide array values for the Boyer-Moore algorithm for the pat- terns below. For simplicity ...

5.2 APPROXIMATE STRING MATCHING 137 position. (Add an r and change the “ad” to an “ea”.) The second position has a 2-approximate ...

138 MATCHING ALGORITHMS sample of this for the substring “trim” and the text “try the trumpet” is given in Fig. 5.9. If we look ...

5.3 PROGRAMMING EXERCISES 139 5.2.2 Construct the approximate matches matrix for substring “their” and text “hello there friend ...

140 MATCHING ALGORITHMS Program up the Boyer-Moore algorithm and count the number of character comparisons done for a few diffe ...

Chapter 6 Graph Algorithms PREREQUISITES Before beginning this chapter, you should be able to Describe a set and set membership ...

142 GRAPH ALGORITHMS STUDY SUGGESTIONS As you are working through the chapter, you should rework the examples to make sure you u ...