龙书的练习3.4.4--失效函数

龙书的练习3.4.4是证明题目所提供的代码的算法正确地计算出了失效函数。代码如下

  t = 0;
  f(1) = 0;
  for(s = 1;s < n; s++){
  while(t >0 && b_s+1 != b_t+1)
    t = f(t);

  if(b_s+1 == b_t+1){
    t = t+1;
    f(s+1) = t;
 }else{
    f(s+1)  =  0;
  }
 }

该函数的目标是使得b_1b_2...b_f(s)是最长的既是b_1b_2...b_s的真前缀又是b_1b_2...b_s的后缀的串。这里为了描述方便我们将b_1b_2...b_f(s)称为最长公共前后缀。

以串ababaa为例，可以算得对应的失效函数值为

f(1)=0
f(2)=0
f(3)=1
f(4)=2
f(5)=3
f(6)=1

下面结合串ababaa说明上述代码为何能实现上述所提及到的目标

1. 代码中第二行f(1)被赋值为零，是因为当s=1时对应的串为a，只有一个字符串显然该串是不存在真前缀的，所以公共前后缀的值为0，即f(1)=0。

2. 第三至第十三行的for循环内的代码主要的目标是计算f(2)至f(6)的值，即当s串分别取值ab aba abab ababa ababaa时对应的失效函数f(s)的值。

while函数，假设在for循环中s的值为s'时，进入while循环并且在第一次判断时,t的值为f(s')。代码的逻辑是当t>0且b_s'+1(s串的第s'+1个字符)与b_t+1(s串的第t+1个字符)不一致时，将t的值赋值为f(t)，t值改变后继续以while括号中的条件进行判断不断重复此过程，直至t=0或b_t+1 == b_s'+1为止。

当然在照着代码的“字面”意思将过程描述处理意义是不大的，描述完代码的过程后要了解代码背后为什么这样做的目的才是最重要。

我们先假设当s'的值是5为例进行说明，此时b_s'+1对应的值为s串ababaa中的最后一个字符，如果你人肉从s=1模拟写到s=5是你会发现此时t对应的值为3。即while第一次进行条件判断时是判断b_s'+1与b_t+1是否相等，即b6与b4的值对应红色框的字符是否相等。

ababaa.png

显然a与b是不相等的，因为f(5)=3，则有f(6)的值不是简单的3+1=4了。为了继续进行判断我们必须缩减t的值再与b6进行判断。此时你可能会产生两个疑问，首先为什么是缩减t的值而不是增加呢？其次如果缩减的话t的值应该是取2或1或 0？

第一个问题f(5)=3已经说明了串ababa的最大公共前后缀为3（如下图绿色和红色表示该情况下的最大公共前后缀），当尝试匹配长度为4的前后缀失败的情况下，长度为5就必然失败了。因此就没必要增加t的值再进行不必要的判断。因为在比对最后一个字符b_s+1与字符b_t+1必然是在b_s+1的前t个字符与长度为t的真前缀一致的情况下，才有进行比对的必要。

ababa.png

第二个问题 通过第二个问题已经知道下一步是缩减t的值但具体要所减到哪个值？如果让我们来实现这个算法的话直觉会从2 1 0递减这样判断，但看上面的代码却采用的是t = f(t)来求得t的值。正如上文所说只有在b_s+1与字符b_t+1必然是在b_s+1的前t个字符与长度为t的真前缀一致的情况下，才有进行比对的必要。

图片.png

以上图为例棕色框的b6与b4的前三个字符都为aba，为此要求得f(6)我们还需要将红线与绿线的范围缩短一下，因为结尾a字符位于串aba之后，因此只需要找到aba的后缀与其真前缀完全一致时的长度就是我们要找的t的值，而通过失效函数即可求得该值，t=f(t)。所以在while代码中才会使用该函数去缩减t的值，直至找到与结尾a字符相等的以a结尾的真前缀为止。

if else代码就相对比较好理解了，当运行while后找到适合跟结尾相等的字符时，t的值也确定了也意味着找到了相应的f(s)，而如果运行完while后没找到与结尾字符相等的字符那么说明找不到在长度为s+1的情况下真前缀与后缀一致的情况，此时对应f(s+1)即为零。

其实失效函数的存在是为了在kmp算法中构造前缀表具体可参考kmp算法。