关于KMP算法预处理功能的实现

Question

只是尝试实现一个KMP算法，但是当我尝试在互联网上检查时，结果发现这里有两个不同的版本:

解决方案1:

function computeLPSArray(str){
    var j = -1, i = 0;
    var arr = [];
    arr[0] = j;
    while(i < str.length){
        if(j == -1||str[i]==str[j]){
            i++;
            j++;
            arr[i] = j;
        } else {
            j = arr[j];
        }
    }
    return arr;
}

解决方案2:

function computeLPSArray(pat){
    var lps = [];
    var len = 0, i;
    lps[0] = 0;
    i = 1;
    while(i < pat.length){
        if(pat[i] == pat[len]){
            len++;
            lps[i] = len;
            i++;
        } else {
            if(len != 0){
                len = lps[len-1];
            } else {
                lps[i++] = 0;
            }
        }
    }
    return lps;
}

解决方案来自极客。为什么不是第一个解决方案?

当我使用解决方案1时，是否有任何角落的情况会失败?

Thx…

Answer 1

并非如此——两个版本都可以用于执行相同的任务。故障链接数组的用法略有不同，但算法的复杂性是相同的，并且两种方法都是正确的。

在其中一种方法中，失败链接是最长正确后缀的长度，也是一个正确前缀(这将是版本2)，而在第一个版本中，它少了1。正如你所看到的，这两个数组是等价的，可以通过加/减1从一个数组转换到另一个数组。