LCS最长公共子序列（输出一条最长子序列）

#include <stdio.h>
#include <iostream.h>
#include <stdlib.h>
#include <string.h>
#define A "xyxxzxyzxy"
#define B "zxzyyzxxyxxz"

void output(char str[])
{
     for(int i=0;i<strlen(str);i++)
         cout<<str[i]<<" ";
     cout<<"\n";
}

int main(void)
{
    char strA[] = {A};
    char strB[] = {B};
    int solution[strlen(A)+1][strlen(B)+1];
   
    output(strA);
    output(strB);
      
    for(int i=0;i<=strlen(A);i++)
    {
        for(int j=0;j<=strlen(B);j++)
            solution[i][j] = 0;
    }
      
    for(int i=1;i<=strlen(A);i++)
    {
        for(int j=1;j<=strlen(B);j++)
        {
            if(strA[i-1] == strB[j-1])
            {
               solution[i][j] = solution[i-1][j-1] + 1;
               if(i == j)
                    cout<<"strA"<<i-1<<strA[i-1]<<" ";
              
            }
            else if(solution[i-1][j]>solution[i][j-1])
            {
                 solution[i][j] = solution[i-1][j];
             }
             else
                 solution[i][j] = solution[i][j-1];       
        }
       
    }
       
    for(int i=0;i<=strlen(A);i++)
    {
        for(int j=0;j<=strlen(B);j++)
            cout<<solution[i][j]<<" ";
        cout<<"\n";
    }  
   
    cout<<"Max Length:"<<solution[strlen(A)][strlen(B)]<<"\n";
    int i = 1;
    int j = 1;
    cout<<"One LCS is :";
    while(i<=strlen(A) && j<=strlen(B))
    {
         if(strA[i-1] == strB[j-1])
         {
            cout<<strA[i-1]<<" ";
            i++;
            j++;
         }     
         else if(solution[i+1][j]>solution[i][j+1])
         {
             i++;
         }      
         else
             j++;     
    }
    cout<<"\n";     
    system( "PAUSE ");
    return 0;
}


需注意的地方是，循环的顺序。