克努特 - 莫里斯 - 普拉特故障表 [英] Knuth-Morris-Pratt Fail table

问题描述

我学习的考试我有，我期待在高德纳 - 莫里斯 - 普拉特算法。这是怎么回事要对考试的失败表和DFA建设。我明白了DFA构造，但我真的不知道如何使故障表。

I am studying for an exam I have and I am looking over the Knuth-Morris-Pratt algorithm. What is going to be on the exam is the Fail table and DFA construction. I understand DFA construction, but I don't really understand how to make the fail table.

如果我有一个模式abababc的例子我如何建立一个从这个失败的表？解决的办法是：

If I have an example of a pattern "abababc" how do I build a fail table from this? The solution is:

失败表：

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

0 0 0 1 2 3 4 0

0 0 0 1 2 3 4 0

但我怎么得到的？没有code如何获取必要只是一个解释。

but how do I get that? No code just an explanation of how to get that is necessary.

推荐答案

字符串取值我的价值code>定义如下：取取值，在位置结束我，和值子在所述细胞是本串的最长正确（不整串）sufix等于相同长度的其preFIX的长度

The value of cell i in the fail table for string s is defined as follows: take the substring of s that ends at position i, and the value in the cell is the length of the longest proper(not the whole string) sufix of this substring that is equal to its prefix of the same length.

让我们把你的榜样，考虑 6 的值。对取值长度为6子是 ABABAB 。它有6后缀： babab ， ABAB ， BAB ， AB 和 B ，另一方面其应有的prefixes是巴， ABAB ， ABA ， AB 和 A 。现在很容易就可以看出这等于相同长度的prefixes的sufixes是 ABAB 和 AB 。这些较长的 ABAB ，因此在小区6的值就是它的长度 - 4 。

Let's take your example and consider the value for 6. The substring of s with length 6 is ababab. It has 6 suffixes: babab, abab, bab, ab and b on the other hand its proper prefixes are ababa, abab, aba, ab and a. Now it is easy to see that the sufixes that are equal to prefixes of the same length are abab and ab. Of these the longer is abab and thus the value in cell 6 is the its length - 4.

这篇关于克努特 - 莫里斯 - 普拉特故障表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！