LCP Array

Problem

Given a string s and its suffix array sa, return the LCP array where entry i is the longest common prefix length of the suffixes starting at sa[i] and sa[i+1].

Use Kasai's algorithm: compute the rank of each suffix, then scan the string maintaining a running prefix length that decreases by at most one per step. Return an empty list when the string has fewer than two characters.

Hint

When moving from suffix i to i + 1, the LCP with the previous suffix drops by at most one.

Test cases

case 1

in: ["banana",[5,3,1,0,4,2]]

expected: [1,3,0,0,2]

case 2

in: ["aaaa",[3,2,1,0]]

expected: [1,2,3]

case 3

in: ["abc",[0,1,2]]

expected: [0,0]

case 4

in: ["a",[0]]

expected: []

case 5

in: ["",[]]

expected: []

Starter codePython

def lcp_array(s, sa):
    # Your code here
    pass

5 test cases · run your code against them in the editor