首页 > 代码库 > diff函数的实现——LCS的变种问题
diff函数的实现——LCS的变种问题
昨天去去哪儿笔试，碰到了一个我们一直很熟悉的命令(diff——ubuntu下面)，可以比较字符串，即根据最长公共子串问题，如果A中有B中没有的字符输出形式如下(-ch),如果A中没有，B中有可以输出如下形式(+ch).
#include <iostream>#include <cstring>#include <vector>using namespace std;string LCS(string &s1, string &s2){ int row = s1.size(); int col = s2.size(); string table[row + 1][col + 1]; char rowChar[row + 1]; char colChar[col + 1]; int cnt = 0; rowChar[0] = colChar[0] = ‘\0‘; for(int i = row - 1, cnt = 1; i >= 0; i--, cnt++) { rowChar[cnt] = s1[i]; } for(int i = col - 1, cnt = 1; i >= 0; i--, cnt++) { colChar[cnt] = s2[i]; } char ch1, ch2; string str1, str2; for(int i = 1; i <= row; i++) { for(int j = 1; j <= col; j++) { ch1 = rowChar[i]; ch2 = colChar[j]; if(ch1 == ch2) table[i][j] = ch1 + table[i - 1][j - 1]; else { str1 = table[i - 1][j]; str2 = table[i][j - 1]; if(str1.size() == str2.size()) table[i][j] = str1 < str2 ? str2 : str1; else table[i][j] = str1.size() < str2.size() ? str2 : str1; } } } return table[row][col];}void showDiff(string &s1, string &s2, string sub, vector<string> &ret){ cout << "Sub = " << sub << endl; int len1 = s1.size(); int len2 = s1.size(); for(int i = 0, j = 0; i < len1; i++) { if(s1[i] != sub[j]) { string str; str.push_back(‘-‘); str.push_back(s1[i]); ret.push_back(str); } else j++; } for(int i = 0, j = 0; i < len2; i++) { if(s2[i] != sub[j]) { string str; str.push_back(‘+‘); str.push_back(s2[i]); ret.push_back(str); } else j++; }}int main(){ string str1, str2; cin >> str1 >> str2; string retSub = LCS(str1, str2); vector<string> ret; showDiff(str1, str2, retSub, ret); vector<string>::iterator iter; for(iter = ret.begin(); iter != ret.end(); iter++) cout << *iter << endl; return 0;}
diff函数的实现——LCS的变种问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。