求两字符串的最长公共序列，，= =。hentai

时间：2011-04-13 来源：Kanone

RT，此算法目前只是针对相对有限的字符串，针对超长的字符串目前还没有进行改进，字符串的最大长度取决于数组的最大大小。。

所以不是很完美，，，很长时间没有编程手生了啊。。。= =，

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

namespace ConsoleApplication1
{
    class Program
    {
        const long t = 1000;                           //t为运算时用的数组的大小，应该不小于两字符串的最大长度，此处定义为1000
        static int[,] c = new int[t + 1, t + 1];
        static int[,] b = new int[t + 1, t + 1];
        static string s = "";

        static void Main(string[] args)
        {
            string X = " ";
            string Y = " ";
            X += "ABCBDAB";                      //此处定义X字符串
            Y += "BDCABA";                       //此处定义Y字符串
            Fuck(X, Y);
            Console.WriteLine("The max length is " +c[ X.Length - 1, Y.Length - 1] + ".\r\n");
            Print(X, Y, X.Length - 1, Y.Length - 1);
            
            Console.ReadKey();
        }

        //运算的函数
        static void Fuck(string X, string Y)
        {
            int m = X.Length - 1;
            int n = Y.Length - 1;

            for (int i = 1; i <= t; i++)
            {
                c[i, 0] = 0;
            }
            for (int j = 0; j <= t; j++)
            {
                c[0, j] = 0;
            }
            for (int i = 1; i <= m; i++)
            {
                for (int j = 1; j <= n; j++)
                {
                    if (X[i] == Y[j])
                    {
                        c[i, j] = c[i - 1, j - 1] + 1;
                        b[i, j] = 2;
                    }
                    else
                    {
                        if (c[i - 1, j] >= c[i, j - 1])
                        {
                            c[i, j] = c[i - 1, j];
                            b[i, j] = 3;
                        }
                        else
                        {
                            c[i, j] = c[i, j - 1];
                            b[i, j] = 1;
                        }
                    }
                }
            }
        }

        //显示输出的函数
        static void Print(string X, string Y, int i, int j)
        {
            string r = s;
            if (i == 0 || j == 0)
            {
                char[] arr = s.ToCharArray();
                Array.Reverse(arr);
                Console.WriteLine(arr);
                s = r;
                return;
            }
            if (b[i, j] == 2)
            {
                s += X[i];
                Print(X, Y, i - 1, j - 1);
            }
            else
            {
                if (b[i, j] == 3)
                {
                    Print(X, Y, i - 1, j);
                    if (b[i, j - 1] == 2)
                    {
                        s = r;
                        Print(X, Y, i, j - 1);
                    }
                }
                else
                {
                    Print(X, Y, i, j - 1);
                }
            }
        }
    }
}