suffix-array - 构建良好的后缀表 - 理解示例

Question

我真的很想了解一个关于如何为给定模式构建良好后缀表的示例。问题是，我无法理解它。我看过很多例子，但不知道这些数字来自哪里。

所以这里是:以下示例演示了如何根据模式 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

非常感谢有关此事的任何帮助。我根本不知道如何获得这些数字。谢谢!

Answer 1

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

第2行我们匹配了N，并且它前面有除A之外的其他内容。现在从末尾开始看一下模式，我们在哪里有N前面有除A之外的其他内容？还有另外两个 N，但两者前面都有 A。这意味着好后缀的任何部分对我们都没有用处——移位完整模式长度 8。

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

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