Shortest common superstring
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
| int getDist(string& from, string& to) {
for(int i = 1; i < from.length(); i++) {
bool included = true;
for(int stFrom = i, stTo = 0; stTo < to.length() and stFrom < from.length() and included; stFrom++, stTo++) {
if(from[stFrom] != to[stTo])
included = false;
}
if(included) {
return to.length() - (from.length() - i);
}
}
return to.length();
}
int Solution::solve(vector<string> &A) {
int n = A.size();
vector<vector<long long>> d(n, vector<long long>(n, INT_MAX));
vector<vector<long long>> dp(1<<n, vector<long long>(n, INT_MAX));
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
d[i][j] = getDist(A[i],A[j]);
}
}
for(int mask = 1; mask< 1<<n; mask++) {
for(int has = 0; has < n; has++) {
if(mask & (1<<has)) {
int maskk = mask ^ (1<<has);
if(maskk == 0) dp[mask][has] = A[has].length();
else {
for(int i = 0; i < n; i++)
dp[mask][has] = min(dp[mask][has], dp[maskk][i] + d[i][has]);
}
}
}
}
int res = INT_MAX;
for(int i = 0; i < n; i++) res = min(res,(int)dp[(1<<n) - 1][i]);
return res;
}
|
