Solution.java

// Stepsort · Kasai's Algorithm
// Category: String
// Animated walkthrough: https://stepsort.prakashraj.me/algorithm/kasai-algorithm

public class Main {
    public static void main(String[] args) {
        String s = "banana";
        int[] sa = {5, 3, 1, 0, 4, 2};
        int n = s.length();
        int[] rank = new int[n], lcp = new int[n];
        for (int i = 0; i < n; i++) rank[sa[i]] = i;
        int h = 0;
        for (int i = 0; i < n; i++) {
            if (rank[i] > 0) {
                int j = sa[rank[i] - 1];
                while (i + h < n && j + h < n && s.charAt(i + h) == s.charAt(j + h)) h++;
                lcp[rank[i]] = h;
                if (h > 0) h--;
            } else h = 0;
        }
        System.out.println(java.util.Arrays.toString(lcp));   // [0, 1, 3, 0, 0, 2]
    }
}