最長公共子序列

//最長公共子序列(個數(shù))
#include<iostream>
using namespace std;
int c[100][100]={0};
int len1,len2;
int  gcd(string a,string b){
    len1=a.length(); 
    len2=b.length();
    int tmp=-1;
    for(int i=0;i<len1;i  )
    {
        for(int j=0;j<len2;j  ){
            if(a[i]==a[j]) c[i][j]=c[i-1][j-1] 1;
            else c[i][j]=max(c[i-1][j],c[i][j-1]);
            if(tmp<c[i][j]) tmp=c[i][j];
        }
    }
    return tmp;
}

int main()
{
    string a,b;
    while(cin>>a>>b){
    cout<<gcd(a,b);    
    }
} 

最長連續(xù)公共子序列

#include<iostream>
#include<string.h>
using namespace std;
 
void print_substring(string str, int end, int length)
{
    int start = end - length   1;
    for(int k=start;k<=end;k  )
        cout << str[k];
    cout << endl;
}
 
int main()
{
    string A,B;
    cin >> A >> B;
    int x = A.length();
    int y = B.length();
    A = " "   A;//特殊處理一下，便于編程 
    B = " "   B;
    
    //回憶一下dp[][]的含義？ 
    int **dp = new int* [x 1];
    int i,j;
    for(i=0;i<=x;i  )
    {
        dp[i] = new int[y 1];
        for(j=0;j<=y;j  )
            dp[i][j] = 0;
    }
    
    
    //下面計(jì)算dp[i][j]的值并記錄最大值 
    int max_length = 0;
    for(i=1;i<=x;i  )
        for(j=1;j<=y;j  )
            if(A[i]==B[j])
            {
                dp[i][j] = dp[i-1][j-1]   1;
                if(dp[i][j]>max_length)
                    max_length = dp[i][j];
            }
            else
                dp[i][j] = 0;
 
    
    //LCS的長度已經(jīng)知道了，下面是根據(jù)這個最大長度和dp[][]的值，
    //找到對應(yīng)的 LCS具體子串， 注意：可能有多個 
    int const arr_length = (x>y?x:y)   1;
    int end_A[arr_length];    //記錄LCS在字符串A中結(jié)束的位置 
    int num_max_length = 0;    //記錄LCS的個數(shù) 
    
    for(i=1;i<=x;i  )
        for(j=1;j<=y;j  )
            if(dp[i][j] == max_length)
                end_A[num_max_length  ] = i;
    
    cout << "the length of LCS(substring) is : " << max_length  << endl << " nums: " << num_max_length << endl << "they are (it is): " << endl;
    for(int k=0;k<num_max_length;k  )    //輸出每個具體的子串 
        print_substring(A, end_A[k], max_length);
    
    return 0;
}

?