algorithm - Boyer-Moore 算法。从课程资源中了解好的后缀转换示例

Question

来自课程资源的好后缀示例。

苏塞纳斯

0 !S = 2

1 !SS = 6

2 !USS = 8

3 !NUSS = 5

其余的 8 个。

我的问题是：为什么 !SS = 6 而不是 = 1，因为 US 在一步匹配 !SS ？

Answer 1

!SS 表示：'SS' 是一个后缀，'xSS' 不是 (x != 'U')。

• 您的文本以“xSS”结尾，您的模式以“USS”结尾

模式右移 1 后：

• 您的文本以“SSy”（未知）结尾，您的模式再次以“USS”结尾

没有 y 的有效值可以使 'SSy' 匹配 'USS'

如果右移 6

• 您的文本以“USSabcde”（未知）结尾，您的模式以“USSENUSS”结尾

如果 'abcde' == 'ENUSS' 这可能匹配