Coincidence(LCS) 最长公共子序列问题
- 题目描述：
-
Find a longest common subsequence of two strings.
- 输入：
-
First and second line of each input case contain two strings of lowercase character a…z. There are no spaces before, inside or after the strings. Lengths of strings do not exceed 100.
- 输出：
-
For each case, output k – the length of a longest common subsequence in one line.
- 样例输入：
-
abcd cxbydz
- 样例输出：
-
2
------------------------------------------------------------------------------------------------------------------------------------------
思想：
dp[ i ][ j ] 代表s1s2...si和t1t2...tj对应的LCS的长度。
状态转移方程：
dp[ i+1 ][ j+1 ]=dp[ i ][ j ]+1 此时Si+1==Sj+1
dp[ i+1 ][ j+1 ]=max(dp[ i+1 ][ j ],dp[ i ][ j+1 ]) 此时Si+1!=Sj+1
Source Code:#include <iostream> #include <string> using namespace std; int maxVal(int a,int b){ return a>b?a:b; } int main() { string str_A,str_B; int dp[110][110]; while(cin>>str_A>>str_B){ unsigned int len_A=str_A.size(); unsigned int len_B=str_B.size(); for(unsigned int i=0;i<=len_A;++i) for(unsigned int j=0;j<=len_B;++j) dp[i][j]=0; for(unsigned int i=0;i<len_A;++i){ for(unsigned int j=0;j<len_B;++j){ if(str_A[i]==str_B[j]) dp[i+1][j+1]=dp[i][j]+1; else dp[i+1][j+1]=maxVal(dp[i+1][j],dp[i][j+1]); } } cout<<dp[len_A][len_B]<<endl; } return 0; }