suffix ACM-ICPC 2017 Asia Qingdao

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 = $suf_1suf1 + suf_2suf2 + · · · + suf_nsufn . 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 $s_1s1 , s_2s2 , · · · , s_nsn . 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.

样例输入

3
3
bbb
aaa
ccc
3
aba
aab
bab
2
abababbaabbababba
abbabbabbbababbab

样例输出

baaac
aaabab
aab

题目来源

ACM-ICPC 2017 Asia Qingdao

https://nanti.jisuanke.com/t/18520

考虑到，每一个字符串起码要选一个后缀，也就是每个字符串的最后一个字符是必须要的

那么，从最后一个字符串开始搞起，每次都从一个字符串的倒数第二个字符开始插入（倒数第一个必须要插入）

然后就相当于给你一个字符串，找出字典序最小的后缀。

设答案后缀下标是ansp，每次插入一个，就需要比较suffix（ansp）和suffix(now)的字典序大小

hash，二分lcp，判断下一位字母大小即可。

复杂度nlogn

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef unsigned long long int LL;
const int maxn = 500000 + 20;
string str[maxn];
char ans[maxn];
unsigned long long int sum[maxn], po[maxn];
const int seed = 131;
int len[maxn];
bool check(int one, int ansp) {
    int be = 1, en = ansp;
    while (be <= en) {
        int mid = (be + en) >> 1;
        if (sum[one] - sum[one - mid] * po[mid] == sum[ansp] - sum[ansp - mid] * po[mid]) {
            be = mid + 1;
        } else en = mid - 1;
    }
//    printf("%d %d
", be, en);
    if (be == ansp + 1) return false;
    return ans[one - en] < ans[ansp - en];
}
char fuck[maxn];
void work() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
//        cin >> str[i];
        scanf("%s", fuck);
        str[i] = string(fuck);
        len[i] = strlen(str[i].c_str());
    }
    int ansp = 0;
    for (int i = n; i >= 1; --i) {
        ans[++ansp] = str[i][len[i] - 1];
        sum[ansp] = sum[ansp - 1] * seed + str[i][len[i] - 1]; //
        int to = 1;
        int t = ansp;
        for (int j = len[i] - 2; j >= 0; --j) {
            ans[ansp + to] = str[i][j];
            sum[ansp + to] = sum[ansp + to - 1] * seed + str[i][j];
            if (check(ansp + to, t)) {
                t = ansp + to;
            }
            to++;
        }
        ansp = t;
//        for (int j = ansp; j >= 1; --j) {
//            printf("%c", ans[j]);
//        }
//        printf("
");
    }
    for (int i = ansp; i >= 1; --i) {
        printf("%c", ans[i]);
    }
    printf("
");
}

int main() {
#ifdef local
    freopen("data.txt", "r", stdin);
//    freopen("data.txt", "w", stdout);
#endif
    po[0] = 1;
    for (int i = 1; i <= maxn - 2; ++i) {
        po[i] = po[i - 1] * seed;
    }
    int t;
    scanf("%d", &t);
    while (t--) work();
    return 0;
}

View Code