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
题目来源
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 = + ;
string str[maxn];
char ans[maxn];
unsigned long long int sum[maxn], po[maxn];
const int seed = ;
int len[maxn];
bool check(int one, int ansp) {
int be = , en = ansp;
while (be <= en) {
int mid = (be + en) >> ;
if (sum[one] - sum[one - mid] * po[mid] == sum[ansp] - sum[ansp - mid] * po[mid]) {
be = mid + ;
} else en = mid - ;
}
// printf("%d %d\n", be, en);
if (be == ansp + ) return false;
return ans[one - en] < ans[ansp - en];
}
char fuck[maxn];
void work() {
int n;
scanf("%d", &n);
for (int i = ; i <= n; ++i) {
// cin >> str[i];
scanf("%s", fuck);
str[i] = string(fuck);
len[i] = strlen(str[i].c_str());
}
int ansp = ;
for (int i = n; i >= ; --i) {
ans[++ansp] = str[i][len[i] - ];
sum[ansp] = sum[ansp - ] * seed + str[i][len[i] - ]; //
int to = ;
int t = ansp;
for (int j = len[i] - ; j >= ; --j) {
ans[ansp + to] = str[i][j];
sum[ansp + to] = sum[ansp + to - ] * 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("\n");
}
for (int i = ansp; i >= ; --i) {
printf("%c", ans[i]);
}
printf("\n");
} int main() {
#ifdef local
freopen("data.txt", "r", stdin);
// freopen("data.txt", "w", stdout);
#endif
po[] = ;
for (int i = ; i <= maxn - ; ++i) {
po[i] = po[i - ] * seed;
}
int t;
scanf("%d", &t);
while (t--) work();
return ;
}
最新文章
- JavaEE学习文章汇总-并发,集群,分布式
- 关于安卓APP的启动界面
- 来聊聊apply和call
- HTML--Table布局
- 可以考虑使用SublimeText编辑器替代notepad++了
- 【转载】MySQL索引原理及慢查询优化
- C语言一个简单的闹钟程序
- 10.31 morning
- Hibernate 关联查询 相关错误
- 对于windows窗口的标题菜单栏的操作——删除/禁用 最小最大话和关闭
- HDU 5723 Abandoned country
- [转载] PHP 线程,进程和并发
- DSAPI 导出EXEDLL函数到字符串
- LODOP中ADD_PRINT_TABLE、HTM、HTML表格自动分页测试
- JS阻止事件冒泡的3种方法之间的不同
- idea导入项目
- javascript 闭包内部机制
- QT 获取电脑时间
- PI Square中文论坛: PI SDK 开发中级篇| PI Square
- 用几分钟了解R语言入门知识