using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithm
{
    class DongTaiGuiHua
    {
        static public int count;
        static public void LCSLength(int m, int n, char[] y, char[] x, int[,] c, char[,] b, char[] LCSString)
        {
            int i=0, j=0;
            for (i = 1; i <=m; i++) c[i,0] = 0;
            for (i = 1; i <=n; i++) c[0,i] = 0;
            for (i = 1; i <=m; i++)
                for (j = 1; j <= n;j++ )
                {
                    if (x[i] == y[j])
                    {
                        c[i,j] = c[i-1,j-1] + 1;
                        b[i,j] = 'x';
                    } 
                    else if (c[i-1,j] >= c[i,j-1])
                    {
                        c[i,j] = c[i-1,j];
                        b[i,j] = 's';
                    }
                    else
                    {
                        c[i,j] = c[i,j-1];
                        b[i,j] = 'z';
                    }
                }
            count = 0;
            LCS(i-1, j-1, x, b, LCSString);
        }
        static public void LCS(int i, int j, char[] x, char[,] b,char [] LCSString)
        {
            if (i == 0 || j == 0) return;
            if (b[i,j] == 'x')
            {
                LCS(i - 1,j - 1, x, b, LCSString);
                LCSString[count++] = x[i];
            }
            else if (b[i,j] == 's') LCS(i - 1, j, x, b, LCSString);
            else LCS(i, j - 1, x, b, LCSString);
        }
    }
}