本文共 3452 字,大约阅读时间需要 11 分钟。
Time Limit:1000MS | Memory Limit:65536K | |||
Total Submissions:5074 | Accepted:2314 | Special Judge |
Description
Input
Output
Sample Input
die einkommen der landwirtesind fuer die abgeordneten ein buch mit sieben siegelnum dem abzuhelfenmuessen dringend alle subventionsgesetze verbessert werden#die steuern auf vermoegen und einkommensollten nach meinung der abgeordnetennachdruecklich erhoben werdendazu muessen die kontrollbefugnisse der finanzbehoerdendringend verbessert werden#
Sample Output
die einkommen der abgeordneten muessen dringend verbessert werden
最长公共子序列。用一个flag数组记录,输出时递归。
#include#include #include #include using namespace std;string str[105];string dest[105];int dp[105][105];int flag[105][105];string result[105];int num;int LCS(int x, int y){ memset(dp,0,sizeof(dp)); memset(flag,-1,sizeof(flag)); int i,j; for(i=1; i<=x; i++) { for(j=1; j <= y; j++) { if(dest[i-1] == str[j-1]) { dp[i][j] = dp[i-1][j-1] + 1; flag[i][j] = 0; } else if(dp[i-1][j] >= dp[i][j-1]) { dp[i][j] = dp[i-1][j]; flag[i][j] = 1; } else { dp[i][j] = dp[i][j-1]; flag[i][j] = 2; } } } return dp[x][y];}void ShowLCS(int x, int y){ if(x == 0 || y == 0) return; if(flag[x][y] == 0) { ShowLCS(x-1,y-1); result[num++] = dest[x-1]; //cout< <<" "; } else if(flag[x][y] == 1) { ShowLCS(x-1,y); } else { ShowLCS(x,y-1); }}int main(){ freopen("in.txt","r",stdin); string s; int dest_len,str_len,i; bool ans = false; while(cin >> s) { memset(dest,0,sizeof(dest)); memset(str,0,sizeof(str)); dest_len = 0; if(s != "#") { dest[dest_len++] = s; ans = false; while(cin >> s) { if(s == "#") { str_len = 0; while(cin >> s) { if(s == "#") { ans = true; break; } str[str_len++] = s; } } else { dest[dest_len++] = s; } if(ans == true) break; } } int ant = LCS(dest_len,str_len); num = 0; ShowLCS(dest_len,str_len); //cout< <
转载地址:http://rtyhj.baihongyu.com/