本文共 2584 字，大约阅读时间需要 8 分钟。
求两个字符串的公共子序列。因为是最基本的算法，所以一次就过了。并且用的是C++的vector和string。。。table数组记录最长公共子序列的长度，如果当前比较的两个字符（本题中为字符串）相当，则table[i][j] = table[i - 1][j - 1] + 1，否则，table[i][j] = max(table[i - 1][j], table[i][j - 1])。table数组的空间肯定可以改进，但想来就挺麻烦的。。。path数组记录路径，0表示当前点包含在最长公共子序列中，1表示向左找，2表示向上找。通过从头往前查path数组就可以构造出最长公共子序列。
注：代码中注释的部分是把一个string按照空格分隔成单词，保存在vector<string>里面，相当于Python或Java里面的split，只是不能指定分隔符。
#include#include #include #include #include using namespace std;string longestcommonsubsequence(const vector &stra, const vector &strb){ int **table = new int*[stra.size()]; for(int i = 0; i < stra.size(); ++i) { table[i] = new int[strb.size()]; } int **path = new int*[stra.size()]; for(int i = 0; i < stra.size(); ++i) { path[i] = new int[strb.size()]; } for(int i = 0; i < stra.size(); ++i) { for(int j = 0; j < strb.size(); ++j) { if(stra[i] == strb[j]) { if(i == 0 || j == 0) { table[i][j] = 1; } else { table[i][j] = table[i - 1][j - 1] + 1; } path[i][j] = 0; } else { if(i == 0 && j == 0) { table[i][j] = 0; path[i][j] = 1; } else if(i != 0 && j == 0) { table[i][j] = table[i - 1][j]; path[i][j] = 1; } else if(i == 0 && j != 0) { table[i][j] = table[i][j - 1]; path[i][j] = 2; } else { int len1 = table[i - 1][j]; int len2 = table[i][j - 1]; if(len1 > len2) { table[i][j] = len1; path[i][j] = 1; } else { table[i][j] = len2; path[i][j] = 2; } } } } } string lcs; bool first = true; for(int i = stra.size() - 1, j = strb.size() - 1; i >= 0 && j >= 0;) { if(path[i][j] == 0) { if(first) { lcs.insert(0, stra[i]); first = false; } else lcs.insert(0, stra[i] + " "); i--; j--; } else if(path[i][j] == 1) { i--; } else { j--; } } return lcs;}int main(){ /* string sentence = "die einkommen der landwirte sind fuer die abgeordneten ein buch mit sieben siegeln um dem abzuhelfen muessen dringend alle subventionsgesetze verbessert werden"; istringstream iss(sentence); vector stra; copy(istream_iterator (iss), istream_iterator (), back_inserter >(stra)); sentence = "die steuern auf vermoegen und einkommen sollten nach meinung der abgeordneten nachdruecklich erhoben werden dazu muessen die kontrollbefugnisse der finanzbehoerden dringend verbessert werden"; //iss.str(sentence); istringstream iss2(sentence); vector strb; copy(istream_iterator (iss2), istream_iterator (), back_inserter >(strb)); */ vector stra, strb; string str; while(true) { stra.clear(); strb.clear(); while(true) { cin>>str; if(cin.eof()) return 0; if(str == "#") break; stra.push_back(str); } while(true) { cin>>str; if(str == "#") break; strb.push_back(str); } cout<
转载地址：http://cxxli.baihongyu.com/