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
  6   |   NPANMAN|   6   | goodCharShift[6]==6
  7   |  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!

Enyedy

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

Goles

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.

Plunger

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.

Alva

In this pdf there is no explanation on how to build the good suffix table – Alda