【UOJ 494】DNA序列（贪心）（Lyndon分解）

DNA序列

题目链接：UOJ 494

题目大意

给你 n 个字符串，要你每个都选一段非空前缀按某种顺序拼在一起使得形成的大字符串字典序最小。

思路

假设如果知道插入的顺序，我们要怎么选前缀。
发现如果前面的 $n-1$ 个都安排好了，那你最后一个选啥是确定的（只选一个字符）
那倒数第一个就确定了，接着看第 $n-1$ 个那你就枚举所有的前缀跟最后一个加一下，选最小的方案。（选最小的准没错，因为不会再后面变劣）
那这样倒着贪心就能构造出字符串。

于是考虑顺序。
那你会发现直观的看我们肯定是先放第一个是 $A$，接着是 $C,G,T$ 这样的。
然后如果那个数的接下来一个小于它，那其实我们应该吧它选上。
然后思考会发现其实它是最大表示串，其实就是 $>$ 为比较的 Lyndon Word。
（因为后缀都比它大那我们把所有前缀循环展开也是前面比它大了）
那我们可以用 Lyndon 分解找到第一个串。

那你可以按这个排序来确定顺序，但是要注意的是这里的也是循环展开比较。
那因为必定不是循环串，我们可以在后面加一个很大的字符，加速上面的操作。

但是还有问题，就是这个 Lyndon Word 可能会一样。
那你考虑一样的内部如何安排顺序，那最后一个的后面可能会放一些东西。
那放啥呢？设 Lyndon Word 是 $s$，那你串可以表示成 $s^k+s^{\prime }$ 的一段前缀，那你就是要让 $s^{\prime }$ 字典序最小（记得也要展开，即加大字符）
那你就直接按 $s^{\prime }$ 从大到小排序即可。

代码

#include
#include
#include
#include

using namespace std;

const int N = 55;
struct node {
	string fir, tail, all;
}a[N];
int n;
char tmp[N];

int getr(int n, int l) {
	int x = l;
	for (int now = l + 1; now <= n; now++) {
		if (tmp[now] > tmp[x]) return now - x;
		if (tmp[x] == tmp[now]) x++;
			else x = 0;
	}
	return n;
}

bool same(int l1, int l2, int sz) {
	for (int i = 1; i <= sz; i++) if (tmp[l1 + i - 1] != tmp[l2 + i - 1]) return 0;
	return 1;
}

bool cmp(node x, node y) {
	if (x.fir != y.fir) return x.fir < y.fir;
	return x.tail > y.tail;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%s", tmp); int m = strlen(tmp); tmp[m] = 'Z';
		int d = getr(m, 0), now = d;
		while (same(0, now, d)) now += d;
		a[i].fir.clear(); a[i].tail.clear();
		a[i].fir = string(tmp, tmp + d) + 'Z';
		a[i].tail = string(tmp + now, tmp + m + 1) + 'Z';
		a[i].all = string(tmp, tmp + m + 1);
//		cout << a[i].fir << endl << a[i].tail << endl;
	}
	
	sort(a + 1, a + n + 1, cmp); string ans;
	for (int i = n; i >= 1; i--) {
		string now = a[i].all[0] + ans;
		string tmp; tmp = tmp + a[i].all[0];
		for (int j = 1; j < a[i].all.size(); j++) {
			tmp = tmp + a[i].all[j]; now = min(now, tmp + ans);
		}
		ans = now;
//		cout << ans << endl;
	}
	cout << ans;
	
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61