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

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

原先写的代码有些问题，这下修改了一次，，但是不是很完美，除了有字符串长度限制以外，有一些情况下的字符串会输出为一样的，主要因为回溯时虽然走了不同的路径，但是由于字符串中有重复的字符出现，导致显示出来的字符串还是一样的，解决办法就是将已经输出的最长公共子序列存起来，之后输出的从这里面进行筛选，没有的话再输出，并且将自己添加进去。。。。= =，，果然蛋疼

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 = " ";
            Console.Write("X: ");
            X += Console.ReadLine(); //此处定义X字符串
            Console.Write("Y: ");
            Y += Console.ReadLine(); //此处定义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);
                if (s.Length == c[X.Length - 1, Y.Length - 1])
                    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);
                }
            }
        }
    }
}