给你一个字符串 s ，找出它的所有子串并按字典序排列，返回排在最后的那个子串。C++实现

可以使用后缀数组来解决这个问题。先构建字符串 s 的后缀数组 sa，并预处理出它的 height 数组。height[i] 表示排名为 i 的后缀与排名为 i-1 的后缀的最长公共前缀。

然后从后往前遍历 height 数组，找到第一个 height[i] 小于 height[i+1] 的位置 i。其实就是找到了子串 s[sa[i]...sa[i]+height[i]] 的结尾在所有子串中排在最后的那个。

C++代码如下：

int sa[N], rk[N], height[N];
int tmp1[N], tmp2[N], c[N];

void build_sa(char *s, int n) {
int m = 256;
for (int i = 0; i < n; ++i) ++c[rk[i] = s[i]];
for (int i = 1; i < m; ++i) c[i] += c[i-1];
for (int i = n-1; i >= 0; --i) sa[--c[s[i]]] = i;
for (int k = 1; k <= n; k <<= 1) {
int num = 0;
for (int i = n-k; i < n; ++i) tmp2[num++] = i;
for (int i = 0; i < n; ++i) if (sa[i] >= k) tmp2[num++] = sa[i]-k;
for (int i = 0; i < m; ++i) c[i] = 0;
for (int i = 0; i < n; ++i) ++c[tmp1[i] = rk[i]];
for (int i = 1; i < m; ++i) c[i] += c[i-1];
for (int i = n-1; i >= 0; --i) sa[--c[tmp1[tmp2[i]]]] = tmp2[i];
swap(rk, tmp1);
rk[sa[0]] = 0; num = 1;
for (int i = 1; i < n; ++i) {
if (tmp1[sa[i]] == tmp1[sa[i-1]] && tmp1[sa[i]+k] == tmp1[sa[i-1]+k])
rk[sa[i]] = num-1;
else
rk[sa[i]] = num++;
}
if (num >= n) break;
m = num;
}
}

void build_height(char *s, int n) {
for (int i = 0; i < n; ++i) rk[sa[i]] = i;
int k = 0;
for (int i = 0; i < n; ++i) {
if (rk[i] == 0) continue;
if (k) --k;
int j = sa[rk[i]-1];
while (s[i+k] == s[j+k]) ++k;
height[rk[i]] = k;
}
}

char s[N];

int main() {
scanf("%s", s);
int n = strlen(s);
build_sa(s, n+1);
build_height(s, n);
int ans = 0;
for (int i = 1; i <= n; ++i) {
if (height[i] < height[i+1]) ans = i;
}
printf("%s\n", s+sa[ans]);
return 0;
}