51nod 1006 最長公共子序列Lcs

#include<bits/stdc++.h>

using namespace std;
//以下為倍增算法求字尾數組
int dp[1100][1100];
char s[1100],s1[1100],s2[1100];
int main(){
 cin>>s;
 cin>>s1;
 int len1=strlen(s);
 int len2=strlen(s1);
 memset(dp,0,sizeof(dp));
 for(int i=0;i<len1;i++)
    for(int j=0;j<len2;j++)
    {
        if(s[i]==s1[j])dp[i+1][j+1]=dp[i][j]+1;
        else dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1]);
    }
    if(dp[len1][len2]==0){printf("\n");return 0;}
    int cnt=0;
    while(dp[len1][len2]>=1)
    {
        if(s[len1-1]==s1[len2-1])
        {
            //printf("%d %d\n",len1,len2);
            s2[cnt++]=s[len1-1];
            len1--;
            len2--;
        }
        else if(dp[len1-1][len2]==dp[len1][len2])len1--;
        else len2--;
    }
        //s2[cnt++]=s[len1-1];
        for(int i=cnt-1;i>=0;i--)
            printf("%c",s2[i]);
    return 0;
}