DEV Community

Discussion on: Algorithms in JavaScript with visual examples.

View post

Replies for: You have an error in LSP value. It must be [0, 0, 0, 3, 5, 0] instead of [0, 0, 0, 1, 2, 0]

Collapse
 
sanzhardanybayev profile image
Sanzhar Danybayev • • Edited

You actually have a wrong LPS algorithm. Here's the right one:

function calculateLpsTable(subStr) {
    let i = 1;
    let j = 0;
    let lps = new Array(subStr.length).fill(0);

    while(i < subStr.length) {
        if(subStr[i] === subStr[j]) {
            lps[i] = j + 1;
            i += 1;
            j += 1;
        } else {
            if(j !== 0) {
                j = lps[j - 1];
            } else {
                i += 1;
            }
        }
    }
    return lps;
}
Enter fullscreen mode Exit fullscreen mode
Collapse
 
swastikyadav profile image
Swastik Yadav •

There was a small typo at line 8. Wrote "i" instead of "1".

Thanks for pointing.