我已经尽力阅读了大部分关于这方面的文献，但仍然不了解 KMP 算法中使用的故障函数是如何构造的。我主要指的是大多数人认为优秀的http://community.topcoder.com/tc ?module=Static&d1=tutorials&d2=stringSearching 教程。但是，我仍然没有理解它。如果您能不厌其烦地给我一个更简单易懂的解释，我将不胜感激。
问问题
9051 次
2 回答
9
失败函数实际上告诉我们：如果匹配字符串的 X 个字符，那么该字符串的最长后缀是什么，它也是搜索字符串的前缀。
您在问它是如何构建的，该方法非常简单。
如果在字符串的末尾添加一个新字符，即您正在构建 f[x]，并且如果它与位置 f[x-1] 的字符匹配，则 f[x] 就是 f[x-1 ]+1。
在其他不匹配的情况下，您尝试找到越来越小的后缀并检查它们是否匹配。
例如，您有一个"accadaccac"要为其构建故障函数的单词，并且您刚刚添加了字母'c'。假设您正在为最后一个字母 the letter 构建一个失败函数'c'。
- 首先查看前一个字母的失败函数，它的失败函数是4，因为你可以匹配suffix
"acca"和prefix"acca"，现在你添加字母'c'，它不匹配'd'后面的字母prefix"acca"。 - 所以你回溯，到最后一个好的后缀。您现在正在搜索的后缀
"acca"也是 的前缀"accadaccac"，但小于“acca”。该问题的答案是 f[length("acca")-1]，或 f[3]，即 f[3] = 1，因为长度为 1 的后缀（只是字母'a'）也是搜索的前缀细绳。 - 现在您可以尝试是否
'c'与位置 1 上的字符匹配，瞧，它匹配，所以现在您知道 f[9] = f[f[8]-1]+1 = 2。
我希望这能帮到您。祝你好运！:)
于 2012-07-01T13:14:48.220 回答
-1
http://www.oneous.com/Tutorial-Content.php?id=24
U can use the learning resources in this website for understanding the KMP Algorithm and the failure function. Also try to take the code and do some runs on it for an example string by hand. However, the best way to understand its working would be to code it yourself on some variations of the basic algorithm. I suggest u start with NHAY and PERIOD on SPOJ.
于 2012-07-03T09:59:37.050 回答