Consider n given non-empty strings denoted by s1 , s2 , · · · , sn . Now for each of them, you need to select a corresponding suffix, denoted by suf1, suf2, · · · , sufn. For each string si, the suffix sufi is a non-empty substring whose right endpoint is the endpoint of the entire string. For instance, all suffixes of the string “jiangsu” are “u”, “su”, “gsu”, “ngsu”, “angsu”, “iangsu” and itself.
All selected suffixes could assemble into a long string T = suf1+ suf2+ · · · +sufn
. Here plus signs indicate additions of strings placing the latter at the tail of the former. Your selections of suffixes would determine the lexicographical order of T . Now, your mission is to find the one with minimum lexicographical order.
Here is a hint about lexicographical order. To compare strings of different lengths, the shorter string is usually padded at the end with enough “blanks” which is a special symbol that is treated as smaller than every letters.
Input
The first line of input contains an integer T which is the total number of test cases. For each case, the first line contains an positive integer n. Each of the following n lines contains a string entirely in lowercase, corresponding to s1, s2, · · · , s n. The summation of lengths of all strings in input is smaller or equal to 500000.
Output
For each test case, output the string T with minimum lexicographical order.
题意：给你n个字符串，你必须按照输入顺序在每个字符串里取一个后缀子串，然后拼接起来，使得其字典序最小，并输出拼接后的字符串。
思路：思路：咋一看好像对每一个字符串求一次sa数组，找到排行第一的那个后缀串，然后拼接起来就ok，但是实际一想，显然不是，比如aabaa cc，如果按照上面的算法，得到aac，但是答案却是aabaac，因为后面的答案会影响前面的后缀串大小，因此我们得先求出最后的最小后缀串，然后将其加到上一个串的结尾，再求前面的串的sa数组再去找最小的后缀串，以此类推再上一个串即可。
#include <bits/stdc++.h> using namespace std; const int maxn = 5e5 + 5; char s[maxn], ans[maxn]; int tx[maxn]; int sa[maxn], rak[maxn]; string str[maxn]; int n, m, p, cnt; struct node { int x, y, id; }a[maxn], b[maxn]; void rsort() { for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[a[i].y]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = 1; i <= n; i++) { b[tx[a[i].y]--] = a[i]; } for (int i = 1; i <= m; i++) { tx[i] = 0; } for (int i = 1; i <= n; i++) { tx[b[i].x]++; } for (int i = 1; i <= m; i++) { tx[i] += tx[i - 1]; } for (int i = n; i >= 1; i--) { a[tx[b[i].x]--] = b[i]; } } void ssort() { rsort(); p = 0; for (int i = 1; i <= n; i++) { if (a[i].x != a[i - 1].x || a[i].y != a[i - 1].y) { ++p; } rak[a[i].id] = p; } for (int i = 1; i <= n; i++) { a[i].x = rak[i]; a[i].id = sa[rak[i]] = i; a[i].y = 0; } m = p; } void solve(int len) { m = 127; n = min(3 * len + 27, cnt); //注意27是必须的，否则会wa掉（我也不知道为什么一定要+27 for (int i = 1; i <= n; i++) { s[i] = ans[cnt - i + 1]; a[i].x = a[i].y = s[i]; a[i].id = i; } ssort(); for (int j = 1; j <= n; j <<= 1) { for (int i = 1; i + j <= n; i++) { a[i].y = a[i + j].x; } ssort(); if (p == n) { break; } } } int main() { int T, q; ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> T; while (T--) { cin >> q; cnt = 0; for (int i = 1; i <= q; i++) { cin >> str[i]; } for (int i = q; i >= 1; i--) { int len = str[i].size(); for (int j = 0; j < len; j++) { ans[++cnt] = str[i][len - j - 1]; } solve(len); int mm = maxn, id = 0; for (int j = 1; j <= len; j++) { if (mm > rak[j]) { mm = rak[j]; id = j; } } cnt -= id - 1; } for (int i = cnt; i >= 1; i--) { cout <<(char)ans[i]; } cout << endl; } return 0; }
