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...

Ivaylo Strandjev · Accepted Answer · 2015-06-09 08:04:28Z

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.

answered Jun 9, 2015 at 8:04

Ivaylo Strandjev

71.4k18 gold badges130 silver badges183 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

About KMP algorithm preprocessing function implementation

Solution 1:

Solution 2:

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

Solution 1:

Solution 2:

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related