最长公共子序列 与 最长公共连续子串

最长公共子序列

//最长公共子序列(个数)#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);        }} 

View Code

最长连续公共子序列

#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;    }            //下面计算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的长度已经知道了，下面是根据这个最大长度和dp[][]的值，    //找到对应的 LCS具体子串， 注意：可能有多个     int const arr_length = (x>y?x:y)   1;    int end_A[arr_length];    //记录LCS在字符串A中结束的位置     int num_max_length = 0;    //记录LCS的个数         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;}

View Code

 

来源：http://www.icode9.com/content-4-111251.html