构建一个好的后缀表 - 理解一个例子

Question

我真的想了解一个如何为给定模式构造一个好的后缀表的例子.问题是,我无法绕过它.我看了很多例子,但不知道数字的来源.

所以这里是:下面的示例演示了如何使用ANPANMAN模式构造一个Good Suffix Table:

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

对此事的任何帮助都非常感谢.我根本不知道如何得到这些数字.谢谢!

Answer 1

第1行,没有匹配的字符,字符读取不是 N.良好后缀长度为零.由于模式中有大量字母也不是N,我们这里的信息很少 - 换1是最不感兴趣的结果.

第2行我们匹配了N,它之前是A之外的其他东西.现在看看从最后开始的模式,我们在哪里有N除了A之外的其他东西？还有另外两个N,但两者都以A开头.这意味着好后缀的任何部分都不会对我们有用 - 按完整模式长度8移动.

第3行:我们匹配AN,并且前面没有M.在模式的中间有一个前面有P的AN,因此它成为移位候选者.将AN向右移动以与我们的比赛对齐是3的转变.

行4及以上:匹配的后缀与模式中的其他内容不匹配,但尾随后缀AN与模式的开头匹配,因此此处的移位均为6.

Answer 2

它可能对您有帮助Good Suffix-Table。

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