题目描述
题目要求找出两个文本的最长公共子序列（LCS，Longest Common Subsequence\texttt{LCS，Longest Common Subsequence}LCS，Longest Common Subsequence），文本由若干单词组成，单词之间用空白分隔，以#结尾。输出任意一个最长公共子序列（单词序列）。
输入格式
输入包含多个测试用例。每个测试用例包含两段文本，每段文本由若干单词组成，以单独一行的#结束。输入以文件结束符（EOF\texttt{EOF}EOF）终止。
输出格式
对于每个测试用例，输出一行，包含最长公共子序列中的单词，单词之间用空格分隔。
样例
输入
die einkommen der landwirte sind fuer die abgeordneten ein buch mit sieben siegeln um dem abzuhelfen mussen dringend alle subventionsgesetze verbessert werden # die steuern auf vermoegen und einkommen sollten nach meinung der abgeordneten nachdrucklich erhoben werden dazu mussen die kontrollbefugnisse der finanzbehoerden dringend verbessert werden #输出
die einkommen der abgeordneten mussen dringend verbessert werden题目分析
本题的核心是求解单词序列的最长公共子序列，并输出子序列本身。
动态规划
设dp[i][j]\textit{dp}[i][j]dp[i][j]表示第一个文本的前iii个单词和第二个文本的前jjj个单词的LCS\texttt{LCS}LCS长度。转移方程：
- 若word1[i]=word2[j]\textit{word1}[i] = \textit{word2}[j]word1[i]=word2[j]，则dp[i][j]=dp[i−1][j−1]+1\textit{dp}[i][j] = \textit{dp}[i-1][j-1] + 1dp[i][j]=dp[i−1][j−1]+1。
- 否则，dp[i][j]=max(dp[i−1][j],dp[i][j−1])\textit{dp}[i][j] = \max(\textit{dp}[i-1][j], \textit{dp}[i][j-1])dp[i][j]=max(dp[i−1][j],dp[i][j−1])。
同时记录路径方向，以便回溯输出单词。
输出
从(n,m)(n, m)(n,m)回溯到(0,0)(0, 0)(0,0)，当遇到相等单词时，将其加入结果列表，最后反转输出。
复杂度分析
单词数n,m≤100n, m \le 100n,m≤100，时间复杂度O(n×m)O(n \times m)O(n×m)，空间复杂度O(n×m)O(n \times m)O(n×m)。
代码实现
// Compromise// UVa ID: 531// Verdict: Accepted// Submission Date: 2016-08-11// UVa Run Time: 0.000s//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);string first[110],second[110];intcommom[110][110][2]={0};while(true){string word;intfirst_count=1;while(cin>>word){if(word=="#")break;first[first_count++]=word;}intsecond_count=1;while(cin>>word){if(word=="#")break;second[second_count++]=word;}if(first_count==1)break;memset(commom,0,sizeof(commom));for(inti=1;i<first_count;i++)for(intj=1;j<second_count;j++){if(first[i]==second[j]&&(commom[i-1][j-1][0]+1)>commom[i][j][0]){commom[i][j][0]=commom[i-1][j-1][0]+1;commom[i][j][1]=1;}if(commom[i-1][j][0]>commom[i][j][0]){commom[i][j][0]=commom[i-1][j][0];commom[i][j][1]=2;}if(commom[i][j-1][0]>commom[i][j][0]){commom[i][j][0]=commom[i][j-1][0];commom[i][j][1]=3;}}vector<string>words;intendi=first_count-1,endj=second_count-1;while(commom[endi][endj][1]>0){if(commom[endi][endj][1]==1){words.push_back(first[endi]);endi-=1,endj-=1;}elseif(commom[endi][endj][1]==2)endi-=1;elseif(commom[endi][endj][1]==3)endj-=1;}reverse(words.begin(),words.end());for(inti=0;i<words.size();i++){if(i>0)cout<<' ';cout<<words[i];}cout<<'\n';}return0;}
