字符串匹配:计算kmp算法中的最长前缀后缀数组

Question

用于字符串匹配的KMP算法.以下是代码,我在网上找到了计算的最长前缀后缀数组:
认定中:

lps[i] = the longest proper prefix of pat[0..i] 
              which is also a suffix of pat[0..i]. 

码:

void computeLPSArray(char *pat, int M, int *lps)
{
    int len = 0;  // length of the previous longest prefix suffix
    int i;

    lps[0] = 0; // lps[0] is always 0
    i = 1;

    // the loop calculates lps[i] for i = 1 to M-1
    while(i < M)
    {
       if(pat[i] == pat[len])
       {
         len++;
         lps[i] = len;
         i++;
       }
       else // (pat[i] != pat[len])
       {
         if( len != 0 )
         {
           // This is tricky. Consider the example AAACAAAA and i = 7.
           len = lps[len-1]; //*****************

           // Also, note that we do not increment i here
         }
         else // if (len == 0)
         {
           lps[i] = 0;
           i++;
         }
       }
    }
}

我可以用len = len-1而不是len = lps[len-1]吗？
因为len总是像[0 .. someIndex]那样计算前缀长度.那么为什么在这里使用lps进行分配呢？以下是我测试哪些工作正常的情况(第一行是模式,后面的两行是原始和修改的赋值的结果len):

a  a  a  b  a  b  c  
0  1  2  0  1  0  0  
0  1  2  0  1  0  0 

a  b  c  b  a  b  c  
0  0  0  0  1  2  3  
0  0  0  0  1  2  3  

a  a  b  c  b  a  b  
0  1  0  0  0  1  0  
0  1  0  0  0  1  0  

代码在这里写了两个变体:http://ideone.com/qiSrUo

Answer 1

以下是它不起作用的情况：

i     0  1  2  3  4  5
p     A  B  A  B  B  A 
c1    0  0  1  2  0  1
c2    0  0  1  2  2  3

原因是：

At i=4, len=2 
p[i]='B' and p[len]='A' //Mismatch!
lps string upto i=3: AB(0-1 prefix), (2-3 suffix)
-------------------------------
i=4
Next charecter: B
len=2 // longest prefix suffix length 
Charecter looking for : A (=p[len])

因此，在 i=3 之前，我们将 AB(0-1) 作为与后缀 AB(2-3) 匹配的前缀，但现在 i=4 时存在不匹配，因此我们看到我们无法扩展原始前缀（ 0-1) 因此要检查的位置是在“AB”之前找到的前缀，这是由 lps[len-1] < -1 完成的，因为数组从 0 > 开始，这不一定是 len-1，因为我们可能需要退一步才能获得新的最长前缀后缀。