Kasai LCP Array

Problem

Compute the LCP array of s with Kasai's algorithm. lcp[i] is the length of the longest common prefix of the suffixes at positions i and i + 1 of the sorted suffix array, so the result has n - 1 entries and is empty when n < 2. Build the suffix array first, then use the inverse permutation and carry the running length over after decreasing it by one.

Hint

When moving from suffix i to i + 1, the LCP with the previous suffix drops by at most one, so total work is linear.

Test cases

case 1

in: ["banana"]

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

case 2

in: ["aaaa"]

expected: [1,2,3]

case 3

in: ["abc"]

expected: [0,0]

case 4

in: ["abab"]

expected: [2,0,1]

case 5

in: [""]

expected: []

Starter codePython

def kasai_lcp(s):
    # Your code here
    pass

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