Building a good suffix table. Understanding the example.
I'm really trying to figure out an example of creating a good suffix table for a given template. The problem is, I can't get my head around me. I've looked through numerous examples, but I don't know where these numbers come from.
So: The following example is a demonstration of how to build a Good Suffix Table based on the ANPANMAN template :
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 greatly appreciated. I just don't know how to get to these numbers. Thank you!
source to share
This can help you Good Suffix-Table .
why didn't you try using the last occurrence method very easily compared to a good suffix table. I used the last input method for my search
source to share
Line 1 , characters do not match, the character read was not N. The length of a good suffix is zero. Since there are many letters in the pattern that are also not N, we have minimal information here - going 1 is the least interesting result.
Line 2 we matched N and was preceded by something other than A. Now look at the pattern starting at the end where we have N, preceded by something other than A? There are two more Ns, but they are preceded by an A. This means that no part of a good suffix can be useful to us - a full-length shift of the pattern 8.
Line 3 . We matched AN and it was not preceded by M. There is an AN in the middle of the pattern that is preceded by P, so it becomes a shift candidate. The shift of this AN to the right to match our match is shift 3.
Lines 4 and up : The matched suffixes do not match anything else in the pattern, but the trailing AN suffix matches the beginning of the pattern, so the shifts are all 6 here.
source to share
While this is an old question and the answer is accepted, I just want to add a pdf from JHU that explains the rules of a good suffix pretty well. http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf
This PDF makes my life so much easier. So hope this helps people who are struggling to understand this algorithm.
source to share