最長公共子序列(LCS)

注意最長公共子串（Longest CommonSubstring）和最長公共子序列（LongestCommon Subsequence, LCS）的區別：子串（Substring）是串的一個連續的部分，子序列（Subsequence）則是從不改變序列的順序，而從序列中去掉任意的元素而獲得的新序列；更簡略地說，前者（子串）的字符的位置必須連續，后者（子序列LCS）則不必。比如字符串acdfg同akdfc的最長公共子串為df，而他們的最長公共子序列是adf。LCS可以使用動態規劃法解決。

學習了http://blog.csdn.net/v_july_v/article/details/6695482的思想，寫了O(mn)的算法

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#define N 105
using namespace std;
int dp[N][N];
string s[2];
int s1,s2;
int Max(int a,int b)
{return a>b?a:b;
}
bool same(int i,int j)
{if(s[0][i]==s[1][j])return true;return false;
}
//如果需要輸出基于最長公共字串的兩串合并，參考hdu1503的AC代碼
string solve()//輸出最長公共字串
{s1=-1,s2=-1;for(int i=0; i<N; i++) for(int j=0; j<N; j++) dp[i][j]=0;for(int i=s[0].length()-1; i>=0; i--)//自上而下遍歷，方便還原的時候順序還原for(int j=s[1].length()-1; j>=0; j--){if(same(i,j)){dp[i][j]=dp[i+1][j+1]+1;if(s1==-1) s1=i;s2=j;
　　　　　　　}elsedp[i][j]=Max(dp[i+1][j],dp[i][j+1]);}string ans="";int i=0,j=0;while(i<s[0].length()&&j<s[1].length()){if(same(i,j))ans+=s[0][i],i++,j++;else{if(dp[i][j+1]>dp[i+1][j])j++;elsei++;}}return ans;
}
int main()
{while(cin>>s[0]>>s[1]){cout<<solve()<<endl;}return 0;
}

?