About KMP algorithm preprocessing function implementation

Question

just try to implement a KMP algorithm, but when I try to check on the Internet, it turns out there are two different versions here:

Solution 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;
}

Solution 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;
}

The solution2 came from geeksforgeeks. Why not first solution?

Is there any corner case will failed when I use the Solution1?

Thx...

Answer 1

Not really - both versions can be used to perform the same tasks. The usage of the failure links array is a bit different, but the complexity of the algorithm is the same and both approaches are correct.

In one of the approaches the fail link is the length of longest proper suffix that is also a proper prefix(this would be version 2), while in the first version it is 1 less. As you can figure the two arrays are equivalent and can be converted from one to the other by adding/subtracting 1.