int N = int(S.size());

vector<int> suffix(N), classes(N);

for (int i = 0; i < N; i++) {

suffix[i] = N - 1 - i;

classes[i] = S[i];

}

stable_sort(suffix.begin(), suffix.end(),

[&S](int i, int j) { return S[i] < S[j]; });

for (int len = 1; len < N; len *= 2) {

vector<int> c(classes);

for (int i = 0; i < N; i++) {

bool same = i && suffix[i - 1] + len < N &&

c[suffix[i]] == c[suffix[i - 1]] &&

c[suffix[i] + len / 2] == c[suffix[i - 1] + len / 2];

classes[suffix[i]] = same ? classes[suffix[i - 1]] : i;

}

vector<int> cnt(N), s(suffix);

for (int i = 0; i < N; i++) {

cnt[i] = i;

}

for (int i = 0; i < N; i++) {

int s1 = s[i] - len;

if (s1 >= 0)

suffix[cnt[classes[s1]]++] = s1;

}

}

return suffix;

int N = int(S.size());

vector<int> rank(N), lcp(N - 1);

for (int i = 0; i < N; i++)

rank[sa[i]] = i;

int pre = 0;

for (int i = 0; i < N; i++) {

if (rank[i] < N - 1) {

int j = sa[rank[i] + 1];

while (max(i, j) + pre < int(S.size()) && S[i + pre] == S[j + pre])

++pre;

lcp[rank[i]] = pre;

if (pre > 0)

--pre;

}

}

return lcp;