string - KMP 算法中使用的 Failure 函数是如何工作的？

Question

我已经尽力阅读了大部分关于这方面的文献，但仍然对 KMP 算法中使用的失效函数是如何构造的一无所知。我主要指的是 http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=stringSearching大多数人认为优秀的教程。但是，我仍然没有理解它。如果您能不厌其烦地给我一个更简单易懂的解释，我将不胜感激。

Answer 1

失败函数实际上告诉我们:如果你匹配了一个字符串的 X 个字符，那么这个字符串的最长后缀是什么，这样它也是一个搜索字符串的前缀。

您问的是它是如何构建的，方法非常简单。

如果你在字符串的末尾添加一个新字符，即你正在构建 f[x]，并且如果它与位置 f[x-1] 的字符匹配，那么 f[x] 就是 f[ x-1]+1.

在其他不匹配的情况下，您尝试找到越来越小的后缀并检查它们是否匹配。

例如，您有一个单词 "accadaccac"，您正在为其构建一个故障函数并且您刚刚添加了字母 'c'。假设您正在为最后一个字母 'c' 构建故障函数。

• 首先检查前一个字母的失败函数，它的失败函数是 4 因为你可以匹配后缀 "acca" 和前缀 "acca"，现在您添加字母 'c'，它与前缀 "acca" 后面的字母 'd' 不匹配。
• 所以你回溯到最后一个好的后缀。您现在正在搜索 "acca" 的后缀，它也是 "accadaccac" 的前缀，但小于 "acca"。该问题的答案是 f[length("acca")-1] 或 f[3]，即 f[3] = 1，因为长度为 1 的后缀(只是字母 'a') 也是搜索字符串的前缀。
• 现在您可以尝试 'c' 是否与位置 1 上的字符匹配，瞧，它匹配，所以现在您知道 f[9] = f[f[8] -1]+1 = 2.

希望对您有所帮助。祝你好运! :)