最短超级串

传送门

题面

给定一个字符串数组 A,找到以 A 中每个字符串作为子字符串的最短字符串。

我们可以假设 A 中没有字符串是 A 中另一个字符串的子字符串。

数据范围

1 <= A.length <= 12

1 <= A[i].length <= 20


题解

一开始想当然先预处理两两字符串之间的重叠部分

e[i][j] 表示 字符串i的后缀 与 字符串j的前缀 的最大重叠长度

找不到什么骚操作,暴力求解了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
for(int i = 0; i < A.size(); ++i)
{
for(int j = 0; j < A.size(); ++j)
{
if(i == j) continue;
int flag = 0;
for(int si = 0; si < A[i].length(); ++si)
{
int p = si, q = 0;
while(p < A[i].length() && q < A[j].length() && A[i][p] == A[j][q]) p++, q++;
if(p == A[i].length())
{
flag = A[i].length()-si;
break;
}
}
e[i][j] = flag;
}
}

之后感觉问题的模型已经出来了

最长路

于是我以 Dijiskra 为原型写了四五遍,最终

发现做不出来…唉,所以比赛就结束了

后来发现最短路的什么三角形法则根本无法适用于最长路

于是又尝试 Bellmand

就发现啊,这是个带0边还有正环的有向图

额,0边没影响,有向也没事,可是正环…不存在最长路…

最终提炼出来的模型是:带正环的图,每个点只能经过一次,求最长路,输出路径

怎么办,最短路算法都没辙,那就…暴力

毕竟数据这么小,想也不是N方算法跑出来的

想法1:枚举每种连接的方案,全排列 O(n!)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int cur, int last, vector<string> &A, string now)
{
if(now.length() > ans.length()) return;
if(cur >= A.size())
{
if(now.length() < ans.length()) ans = now;
return;
}

for(int i = 0; i < A.size(); ++i)
{
if(vis[i]) continue;
vis[i] = 1;
dfs(cur+1, i, A, now+A[i].substr(e[last][i]));
vis[i] = 0;
}
}

妥妥T了

想法2: 状压DP O(N^2*2^N)

一直卡了一星期终于做出来…

定义状态 dp[i][s]

s表示二进制下当前以及访问过的点,i表示当前状态下最后访问的点,存储的值表示当前最小长度

状态转移方程: dp[i][s] = min( dp[j][s^(1<<i)] + A[j].length() - e[j][i] )

二进制的骚操作不多说了,其中j是s中访问过的某个点

初始化: dp[i][1<<i] = A[i].length(), 其余设为 INF(无穷大)

最终结果: max( dp[i][(1<<A.size())-1])

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
memset(dp, 0x3f, sizeof dp);
memset(last, -1, sizeof last);
for(int i = 0; i < A.size(); ++i) dp[i][0] = 0, dp[i][1<<i] = A[i].length();
for(int i = 1; i < (1<<A.size()); ++i)
for(int now = 0; now < A.size(); ++now)
if(i&(1<<now))
for(int pre = 0; pre < A.size(); ++pre)
if((i&(1<<pre)) && now != pre)
{
int tmp = dp[pre][i^(1<<now)]+A[now].length()-e[pre][now];
if(dp[now][i] > tmp)
{
dp[now][i] = tmp;
last[now][i] = pre;
}
}

int resi = 0, nows = (1<<A.size())-1;
for(int i = 1; i < A.size(); ++i)
if(dp[i][nows] < dp[resi][nows])
resi = i;
cout << dp[resi][nows] << endl; //////

然后还有一个头疼的地方是输出路径

last[i][s] 记录一下前驱,就是记录 j

倒过来找,再翻回去,这样就求出了字符串的排列

1
2
3
4
5
6
7
8
9
10
vector<int> ress;
while(resi != -1)
{
cout << resi << " ";// << nows << endl; ///////
ress.push_back(resi);
// 此处需注意 resi 和 nows 是否改变
nows ^= 1<<resi;
resi = last[resi][nows|(1<<resi)];
}
reverse(ress.begin(), ress.end());

最后是拼起来,这个也容易

仔细观察两个字符串拼起来的就是 A[i]+A[j].substr(e[i][j])


代码

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
62
63
64
65
66
67
68
69
70
71
72
class Solution {
public:
static const int Maxn = 13;
int e[Maxn][Maxn], dp[Maxn][1<<Maxn], last[Maxn][1<<Maxn];

string shortestSuperstring(vector<string>& A) {
for(int i = 0; i < A.size(); ++i)
{
for(int j = 0; j < A.size(); ++j)
{
if(i == j) continue;
int flag = 0;
for(int si = 0; si < A[i].length(); ++si)
{
int p = si, q = 0;
while(p < A[i].length() && q < A[j].length() && A[i][p] == A[j][q]) p++, q++;
if(p == A[i].length())
{
flag = A[i].length()-si;
break;
}
}
e[i][j] = flag;
}
}
/*/debug
for(int i = 0; i < A.size(); ++i)
{
for(int j = 0; j < A.size(); ++j)
cout << e[i][j] << " ";
cout << endl;
}
//debug */
memset(dp, 0x3f, sizeof dp);
memset(last, -1, sizeof last);
for(int i = 0; i < A.size(); ++i) dp[i][0] = 0, dp[i][1<<i] = A[i].length();
for(int i = 1; i < (1<<A.size()); ++i)
for(int now = 0; now < A.size(); ++now)
if(i&(1<<now))
for(int pre = 0; pre < A.size(); ++pre)
if((i&(1<<pre)) && now != pre)
{
int tmp = dp[pre][i^(1<<now)]+A[now].length()-e[pre][now];
if(dp[now][i] > tmp)
{
dp[now][i] = tmp;
last[now][i] = pre;
}
}

int resi = 0, nows = (1<<A.size())-1;
vector<int> ress;
string res;

for(int i = 1; i < A.size(); ++i)
if(dp[i][nows] < dp[resi][nows])
resi = i;
cout << dp[resi][nows] << endl; //////
while(resi != -1)
{
cout << resi << " ";// << nows << endl; ///////
ress.push_back(resi);
nows ^= 1<<resi;
resi = last[resi][nows|(1<<resi)];
}
reverse(ress.begin(), ress.end());
res = A[ress[0]];
for(int i = 1; i < ress.size(); ++i)
res += A[ress[i]].substr(e[ress[i-1]][ress[i]]);
return res;
}
};
求抱养
0%