Constructing a Good Suffix Table - Understanding an example

Question

I'm really trying to understand an example on how to construct a good suffix table for a given pattern. The problem is, I'm unable to wrap my head around it. I've looked at numerous examples, but do not know where the numbers come from.

So here goes: The following example is a demonstration of how to construct a Good Suffix Table given the pattern ANPANMAN:

Index | Mismatch | Shift | goodCharShift
-----------------------------------------------
  0   |         N|   1   | goodCharShift[0]==1
  1   |        AN|   8   | goodCharShift[1]==8
  2   |       MAN|   3   | goodCharShift[2]==3
  3   |      NMAN|   6   | goodCharShift[3]==6
  4   |     ANMAN|   6   | goodCharShift[4]==6
  5   |    PANMAN|   6   | goodCharShift[5]==6
  0   |   NPANMAN|   6   | goodCharShift[6]==6
  0   |  ANPANMAN|   6   | goodCharShift[7]==6

Any help on this matter is highly appreciated. I simply don't know how to get to these numbers. Thanks!

Answer 1

It might help you Good Suffix-Table.

why you didnt try with last occurrence method its much easy as compared to good suffix table.I used last occurrence method for my searching

Answer 2

Row 1, no characters matched, the character read was not an N. The good-suffix length is zero. Since there are plenty of letters in the pattern that are also not N, we have minimal information here - shifting by 1 is the least interesting result.

Row 2 we matched the N, and it was preceded by something other than A. Now look at the pattern starting from the end, where do we have N preceded by something other than A? There are two other N's, but both are preceded by A. That means no part of the good suffix can be useful to us -- shift by the full pattern length 8.

Row 3: We matched the AN, and it was preceded by not M. In the middle of the pattern there is a AN preceded by P, so it becomes the shift candidate. Shifting that AN to the right to line up with our match is a shift of 3.

Rows 4 & up: the matched suffixes do not match anything else in the pattern, but the trailing suffix AN matches the start of the pattern, so the shifts here are all 6.

Answer 3

Although, this is an old question and there is an answer being accepted, but I just want to add the pdf from JHU, which explains quite well about the good suffix rules. http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

This pdf makes my life so much easier. So hope that it will help people who are struggling with understanding this algorithm as well.