string - KMP算法中使用的故障功能如何工作？

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

最佳答案

故障函数实际上告诉我们:如果您匹配一个字符串的X个字符，那么该字符串的最长后缀是什么，使得它也是搜索字符串的前缀。

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

如果在字符串末尾添加新字符，即正在构建f [x]，并且如果它与位置f [x-1]处的字符匹配，则f [x]就是f [x-1 ] +1。

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

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

首先检查前一个字母的失败函数，因为您可以将后缀"acca"与前缀"acca"匹配，所以它的失败函数为4，现在添加字母'c'，它与后面的前缀'd'的字母"acca"不匹配。

因此，您可以回溯到最后一个很好的后缀。现在，您正在搜索"acca"的后缀，它也是"accadaccac"的前缀，但小于“acca”。该问题的答案是f [length(“acca”)-1]或f [3]，即f [3] = 1，因为长度为1的后缀(只是字母'a')也是a的前缀搜索字符串。

现在，您可以尝试将'c'与位置1上的字符匹配，将其与voila匹配，因此现在您知道f [9] = f [f [8] -1] +1 = 2。

我希望这能帮到您。祝你好运! :)