Errata

Killer ones

1. In page 50, line 12, "ut_{i+1}" should be "vt_{i+1}".
2. In page 71, Fig 3.21 contains a mistake (which actually does not compromise correctness, but does not match the explanation nor the examples). In line 21, it should read "pos <- pos+j+1". As a consequence, line 19 should now be removed. Finally, one can only leave the condition "Current != theta" in line 17, because the check for j=0 is unnecessary and the last check is unnecessary as well as the oracle does not recognize spurious strings of the length of the pattern.
3. In page 127, Fig. 5.21 contains several mistakes. Line 3 should be deleted. Line 12 should be "Trie <- new root node". In line 10, "Next" should be "delta(Trie,sigma)". Besides, Trie should be rather called Node in Pref, as it is recursive.
4. In page 128, Fig. 5.22, line 9. Missing instruction "j <- j+1".
5. In page 134, the code of Fig 5.26 has a mistake. There should be a line " j <- j+1" between lines 16 and 17 (inside the While of line 16).
6. In page 153, the formula for R'_i in line 3 lacks an "| 0^{m-1}1" at the end, to account for the unrepresented initial state. The same correction is needed in line 11 of Figure 6.6.
7. In page 155, line -10, "rightmost" should be "leftmost", and vice versa in line -8.
8. In pages 157-158, there is an error in the example. The 4 blocks that make up table BB are reversed (although D is correct). For example, BB[a] = 0101 0011 0111 0110 and it should be 0110 0111 0011 0101.
9. In page 172, lines 1 and 2, one initial character is missing from the signatures. It is t_{i+1} in the first (line 1) and t_i in the rest (line 2).
10. In page 172, it should be said that existence in the hash table is a necessary condition for a match, but not a sufficient one, so verification is necessary. For example the pattern "abcde" would match "abcxd".

Stupid ones

1. In page 21, Fig. 2.7, the caption should rather say "Nondeterministic automaton recognizing strings terminating with 'announce', that is, text positions where an occurrence of 'announce' ends.".
2. In page 25, Fig. 2.11, the double arrow labeled "no beta in this part" should not stretch over the last character of the pattern, as this is ignored.
3. In page 26, in the example on DNA, it reads "m=8", where it is obviously m=5.
4. In page 30, although it doesn't say so explicitly, it leads one to understand that bit d(j) = 1 iff p(j)...p(j+|u|-1) = u. The representation is reversed, so d(j) should instead be d(m-j+1). See that, otherwise, d(m) = 1 does not imply a prefix match.
5. In page 31, caption of Fig. 2.17, the NFA recognizes all suffixes, not factors, of the reversed string.
6. In page 33, point 1., it is not signaled that we should set last <- 4 after reading the first "A" of the window.
7. In page 53, item 6 of the example on English, should read delta(7,l) instead of delta(7,a).
8. In page 54, item 15 of the example on DNA, when it reads 1 = S_{AC}(7) it should read 5 = S_{AC}(7). delta(5,C) = theta; we jump to 1 = S_{AC}(5).
9. In page 56, Fig 3.13, as in Fig 2.11, the arrow labeled "no beta in this part" should not stretch over the first level of the trie.
10. In page 59, on lines -2 and -3, B should be Bl.
11. In page 64, Figure 3.19, we have used masks of size |P|, while in fact they have size r * lmin. Also, the argument should be P = { p^1, p^2, ..., p^r }, not p = p_1 p_2 ... p_m.
12. In page 84, caption of Fig. 4.4 should say "suffixes", not "factors".
13. In page 89, line 9, "1^{x-y+1}0^{z+1}" should be "1^{y+1}0^{z+1}".
14. In page 106, caption of Fig. 5.5, the regular expression is wrong. It should be (AT|GA)((AG|AAA)*).
15. In page 114 (Section 5.3.2), it is said that the DFAs of Figure 5.12 are minimal. This is wrong. All the final states could be merged into one, and then some states with arrows to final states, etc.
16. In page 116, "DFAModules" should be "NFAModules".
17. In page 119, Eq. (5.4), [0...m] should be [0..L-1].
18. In page 120, it is written E[11] = 111001101100000000, while, as it can be seen in table E_n of page 121, E[11] = 110001101100010011. Differences in bits 0, 1, and 4 (counting from the right) are ok because in page 121 we include E(0) in all masks, but bit 15 should be zero in page 120.
19. In page 173, line -1, the condition of applicability is actually alpha < 1/log_|Sigma| (rm).

Forgiveable ones

1. Still there are several "search" that should have been "search for".
2. In page 18, line 5, it reads "what what".
3. In page 56, Fig 3.13 should say "Trie of reverse patterns" instead of "Reverse trie of the patterns".
4. In page 58, the small table at the left end of the page should be called d, not delta.
5. In page 69, SDBM -> SBDM.
6. In page 72, item 7 of example on English, "conferencea_" should be "conference_a".
7. In page 82, line 9, what reads "to find patterns quickly patterns with gaps" should be "to find patterns with gaps fast".
8. In page 90, line -6, an opening parenthesis is missing in the beginning of the right hand of the assignment.
9. In page 92, line 33 of code in Fig 4.9, same error of page 90.
10. In page 105, beginning of 5.2.2., "by popularized" should be "popularized by".
11. In page 110, Fig 5.9, line 9, "final" is better than "terminal" in this context.
12. In page 130, the correct term "necessary set of factors" is sometimes replaced by the less fortunate term "set of necessary factors", which is not so good because no individual factor in the set is necessary. Also, in line -8, word "all" should have been in italics.
13. In pages 159 and 160, P_i and T_j should better be p_i and t_j.
14. In page 140, the parser assumes that the regular expression is fully parenthesized (which is not said). Otherwise, a fully recursive parser is probably needed, i.e., first regard the string as a sequence of terms separated by |s, then parse each term as a sequence of factors separated by the implicit .s, and finally each factor as a letter suffixed with zero or more *s, or instead again a full regexp within ()'s.
15. In page 163, line -9, "i2" should be "i_2".
16. In page 211, reference [FNU01] appears incorrectly as a book, while it is a chapter of book Recent Research Developments in Pattern Recognition, by S. Pandalai (editor).
17. In page 220, the first entry "DFAModules" to page 115 should actually appear under "NFAModules", as the term "DFAModules" was a mistake.