lcs.cpp

最长公共子序列算法LCS实现。任意输入两个字符串

/*the longest comman sequence 
 *input :two string s, t, length are n,m respectively
  
             0                          if i = 0 or j = 0   
 *c[i][j] = { c[i-1][j-1] + 1            if s[i] = t[j]
             max(c[i][j-1],c[i-1][j])   if s[i] != t[j]
 
 *output: return c[n][m]
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX 100
 
char str1[MAX], str2[MAX];
char B[MAX][MAX];
int  l1[MAX],l2[MAX];

int LCS(char *s,char *t)
{
    int i, j, k;
    int ls = strlen(s+1),lt = strlen(t+1);
    //printf("%d %d\n",strlen(s),strlen(t));
    
    //printf("%d %d",ls,lt);
    
    
    for(i=0; i<=lt; i++)
             l1[i] = 0;
             
    for(i=1; i<=ls; i++)
    {
             for(j=1; j<=lt; j++)
             {
                      if(s[i] == t[j])
                      {
                              l2[j] = l1[j-1] + 1;
                              B[i][j] = '1';
                      }
                      else
                      {
                          if(l2[j-1]>l1[j])
                          {
                              l2[j] = l2[j-1];
                              B[i][j] = '2';
                          }
                          else
                          {
                              l2[j] = l1[j];
                              B[i][j] = '3';
                          }
                      }
             }
             for(k=0; k<=lt; k++)
             {
                      l1[k] = l2[k];
             }
    }    
    return l2[lt];
}

void Construct(char *s,char b[][MAX], int n, int m)
{
     if(n==0||m==0)
     {
           return ;
     }
     
     else
     {
         if(b[n][m] == '1')
         {      
               Construct(s,b,n-1,m-1);
               printf("%c",s[n]);
         }
         else if(b[n][m] =='2')
         {
              Construct(s,b,n,m-1);
         }
         else
         {
             Construct(s,b,n-1,m);
         }
     }
}

int main()
{
    
    printf("请输入第一个字符串 :\n"); 
    scanf("%s",str1+1);
    printf("请输入第二个字符串 :\n");
    scanf("%s",str2+1); 
    printf("最长公共子序列的长度 :%d\n",LCS(str1, str2));
    printf("最长公共子序列 :");
    Construct(str1,B,strlen(str1+1),strlen(str2+1));
    
    while(1);
    return 0;
}