本文共 2230 字，大约阅读时间需要 7 分钟。
21st Century Fruits公司专注于通过基因转移创造新的水果种类，往往失败，但有时会产生极为罕见的新品，这些新品的味道是两种水果的结合。公司内部的讨论重点之一就是“如何命名新品”。比如，将苹果和梨混合，可以直接叫“苹果梨”，但听起来缺乏趣味。因此，公司决定使用最短的字符串，将两个水果的名字作为子序列存在。例如，“applear”既包含“苹果”（APPLEar）又包含“梨”（apPlEAR），并且没有比这更短的满足条件的字符串。
对于柑橘和boysenberry的结合，新的名字可以是“boysecranberry”或“craboysenberry”等。你的任务是编写一个程序，计算这样的最短名字。算法需要高效，否则在处理长水果名称时可能无法在规定时间内完成。
每行输入包含两个字符串，表示需要结合的水果名称。所有名称的最大长度为100，只包含字母。输入结束于文件结束。
对于每个测试用例，输出最短的名称。如果有多个最短的名字，任何一个都可以。
apple peachananas bananapear peach
appleachbananaspeach
这个问题实际上是寻找两个字符串的最长公共子序列（LCS）。LCS是一条既包含第一个字符串中的某些字符序列，又包含第二个字符串中某些字符序列的序列。我们可以使用动态规划算法来计算LCS，然后将两个字符串中的字符按照LCS的顺序合并，得到最短的新名称。
具体来说，我们可以创建一个二维数组dp，其中dp[i][j]表示第一个字符串的前i个字符和第二个字符串的前j个字符的最长公共子序列的长度。同时，我们可以创建一个方向数组dir来记录每个位置的字符来自第一个字符串还是第二个字符串。
然后，我们可以按照LCS的结果，将两个字符串中的字符按照记录的顺序合并，生成最短的新名称。
#include#include #include #include using namespace std;void LCS_length(string x, string y, vector >& dp, vector >& dir) { int m = x.size(); int n = y.size(); dp.resize(m + 1); dir.resize(m + 1); for (int i = 0; i <= m; ++i) { dp[i].resize(n + 1); dir[i].resize(n + 1); } for (int i = 1; i <= m; ++i) { for (int j = 1; j <= n; ++j) { if (x[i-1] == y[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; dir[i][j] = 'c'; } else if (dp[i-1][j] > dp[i][j-1]) { dp[i][j] = dp[i-1][j]; dir[i][j] = 'u'; } else { dp[i][j] = dp[i][j-1]; dir[i][j] = 'l'; } } }}void dp_print_lcs(const vector >& dir, const string& x, const string& y, int i, int j) { if (i == 0 && j == 0) return; if (dir[i][j] == 'c') { dp_print_lcs(dir, x, y, i-1, j-1); cout << x[i-1]; } else if (dir[i][j] == 'u') { dp_print_lcs(dir, x, y, i-1, j); cout << y[j-1]; dp_print_lcs(dir, x, y, i, j-1); }}int main() { string x, y; while (cin >> x >> y) { vector > dp(m + 1, vector (n + 1, 0)); vector > dir(m + 1, vector (n + 1, '\0')); LCS_length(x, y, dp, dir); string result; if (dir[m][n] > 0) { dp_print_lcs(dir, x, y, m, n); } cout << result << endl; }}
dir的记录，按照LCS顺序输出结果字符串。这个算法的时间复杂度是O(m*n)，其中m和n是两个字符串的长度。由于水果名称的最大长度为100，该算法在时间和空间上都是高效的，能够在规定时间内处理所有输入。
转载地址：http://ygta.baihongyu.com/