8

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!

4

3 回答 3

10

第 1 行，没有匹配的字符，读取的字符不是N。好后缀长度为零。由于模式中有很多字母也不是 N，所以我们这里的信息很少 - 移动 1 是最不有趣的结果。

第 2 行我们匹配了 N，它前面有 A 以外的东西。现在看看从末尾开始的模式，我们在哪里 N 前面有 A 以外的东西？还有另外两个 N，但都以 A 开头。这意味着 good 后缀的任何部分对我们都没有用 - 移位整个模式长度 8。

第 3 行：我们匹配了 AN，它前面不是 M。在模式的中间有一个 AN 前面是 P，所以它成为移位候选。将 AN 向右移动以与我们的比赛对齐是 3 的移动。

第 4 行及以上：匹配的后缀不匹配模式中的任何其他内容，但尾随后缀 AN 匹配模式的开头，因此这里的移位都是 6。

于 2017-03-10T14:49:50.677 回答
3

它可能会帮助你Good Suffix-Table。

为什么你没有尝试使用最后出现的方法，它比好的后缀表容易得多。我使用最后出现的方法进行搜索

于 2015-05-16T15:14:40.817 回答
0

虽然，这是一个老问题，并且有一个答案被接受，但我只想添加 JHU 的 pdf，它很好地解释了良好的后缀规则。 http://www.cs.jhu.edu/~langmea/resources/lecture_notes/boyer_moore.pdf

这个 pdf 让我的生活变得轻松多了。所以希望它能帮助那些也在努力理解这个算法的人。

于 2019-06-18T10:19:09.213 回答