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',它与字母'd'后续前缀不匹配"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.

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