Suffix Array (접미사 배열)

def build_sa(s):
  n = len(s)
  sa = list(range(n))
  rank = [ord(c) for c in s]
  tmp = [0] * n
  k = 1
  while k < n:
      sa.sort(key=lambda x: (rank[x], rank[x + k] if x + k < n else -1))
      tmp[sa[0]] = 0
      for i in range(1, n):
          prev, cur = sa[i-1], sa[i]
          pk = rank[prev + k] if prev + k < n else -1
          ck = rank[cur + k] if cur + k < n else -1
          tmp[cur] = tmp[prev] + (rank[prev] != rank[cur] or pk != ck)
      rank = tmp
      k <<= 1
  return sa
​
def build_lcp(s, sa):
  n = len(s)
  rank = [0] * n
  for i, pos in enumerate(sa): rank[pos] = i
  lcp, k = [0] * n, 0
  for i in range(n):
      if rank[i] == 0: continue
      j = sa[rank[i] - 1]
      while i + k < n and j + k < n and s[i+k] == s[j+k]: k += 1
      lcp[rank[i]] = k
      if k: k -= 1
  return lcp
​
s = input().strip()
sa = build_sa(s)
lcp = build_lcp(s, sa)
print(*sa)
print(*lcp)

import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String s = br.readLine();
      int n = s.length();
      Integer[] sa = new Integer[n];
      int[] rank = new int[n], tmp = new int[n];
      for (int i = 0; i < n; i++) { sa[i] = i; rank[i] = s.charAt(i); }
      for (int k = 1; k < n; k *= 2) {
          final int K = k;
          final int[] R = rank;
          Arrays.sort(sa, (a, b) -> {
              if (R[a] != R[b]) return Integer.compare(R[a], R[b]);
              return Integer.compare(a+K<n?R[a+K]:-1, b+K<n?R[b+K]:-1);
          });
          tmp[sa[0]] = 0;
          for (int i = 1; i < n; i++) {
              int a = sa[i-1], b = sa[i];
              boolean diff = R[a] != R[b] || (a+K<n?R[a+K]:-1) != (b+K<n?R[b+K]:-1);
              tmp[b] = tmp[a] + (diff ? 1 : 0);
          }
          rank = tmp;
      }
      StringBuilder sb = new StringBuilder();
      for (int x : sa) sb.append(x).append(" ");
      System.out.println(sb);
  }
}