?

1006?最長公共子序列Lcs?

基準時間限制：1?秒 空間限制：131072?KB 分值:?0?難度：基礎題

給出兩個字符串A B，求A與B的最長公共子序列（子序列不要求是連續的）。

比如兩個串為：

abcicba

abdkscab

ab是兩個串的子序列，abc也是，abca也是，其中abca是這兩個字符串最長的子序列。

Input

第1行：字符串A 第2行：字符串B (A,B的長度?<=?1000)

Output

輸出最長的子序列，如果有多個，隨意輸出1個。

Input示例

acbcf abcdaf

Output示例

abcf

題意已經非常清楚了，主要考察dp的去的過程和回來的過程。即先找的其最長的lcs的長度，再反過去找其被標記的字符串。

現在附以下圖示：

?

#include<stdio.h> #include<algorithm> #include<string.h> using namespace std; int i,j; int l1,l2; char s1[1005],s2[1005]; int main() {while(~scanf("%s%s",s1,s2)){l1=strlen(s1);l2=strlen(s2);int dp[l1+5][l2+5];memset(dp,0,sizeof(dp));for( i=1;i<=l1;i++){for(j=1;j<=l2;j++){if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+1;elsedp[i][j]=max(dp[i-1][j],dp[i][j-1]);}}int k=dp[l1][l2];char lcs[1001]={'\0'};i--;j--;while(i&&j){if(s1[i-1]==s2[j-1]&&dp[i][j]==dp[i-1][j-1]+1){lcs[--k]=s1[i-1];i--;j--;}else if(s1[i-1]!=s2[j-1]&&dp[i-1][j]>dp[i][j-1])//上圖已經非常清楚了i--;elsej--;}printf("%s\n",lcs);}return 0; }

?

總結

以上是生活随笔為你收集整理的51node1006LCS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。