手机版
你好,游客 登录 注册
背景:
阅读新闻

C# 最长公共子序列

[日期:2014-10-15] 来源:Linux社区  作者:luozuolincool [字体: ]

C#  最长公共子序列

本程序实现了字符串的最长公共子序列的方法:str[i,j]数组中保存str1,str2长度分别为0-i,0-j之间的最长公共子序列,s[i,j]数组中保存str1,str2长度分别为0-i,0-j之间的最长公共子序列的长度;

s[i,j]=0,i=0或者j=0
s[i,j]=s[i - 1, j - 1] + 1;str1[i]=str2[j]
s[i,j]=max{s[i - 1, j ],s[i , j-1 ] };str1[i]!=str2[j]

代码如下
 class Program
    {
        static void Main(string[] args)
        {
            String[,] str = LCS("bdcaba", "abcbdab");
            for (int i = 0; i < str.GetLength(0); i++)
            {
                for (int j = 0; j < str.GetLength(1); j++)
                {
                    Console.WriteLine(i+" "+j+" "+str[i,j]);
                }
            }
            Console.Read();
        }
        static String[,] LCS(String str1,String str2)
        {
            int[,] s = new int[str1.Length+1, str2.Length+1];
            String[,] str = new String[str1.Length + 1, str2.Length + 1];
            for (int i = 0; i <= str1.Length; i++)
            {
                for (int j =0; j <= str2.Length; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        s[i, j] = 0;
                        str[i, j] = "";
                    }
                    else
                    {
                        if (str1.Substring(i - 1, 1) == str2.Substring(j - 1, 1))
                        {
                            s[i, j] = s[i - 1, j - 1] + 1;
                            str[i, j] = str[i - 1, j - 1] + str1.Substring(i - 1, 1);
                        }
                        else
                        {
                            s[i, j] = s[i - 1, j] > s[i, j - 1] ? s[i - 1, j] : s[i, j - 1];
                            str[i, j] = s[i - 1, j] > s[i, j - 1] ? str[i - 1, j] : str[i, j - 1];
                        }
                    }
                }
            }
            return str;
        }
    }

下面是输出结果截图:

C#  最长公共子序列

C#多线程编程实例 线程与窗体交互【附源码】 http://www.linuxidc.com/Linux/2014-07/104294.htm

C#数学运算表达式解释器 http://www.linuxidc.com/Linux/2014-07/104289.htm

C语言中解析JSON配置文件 http://www.linuxidc.com/Linux/2014-05/101822.htm

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码 http://www.linuxidc.com/Linux/2014-05/101227.htm

本文永久更新链接地址http://www.linuxidc.com/Linux/2014-10/108085.htm

linux
相关资讯       C#  最长公共子序列 
本文评论   查看全部评论 (0)
表情: 表情 姓名: 字数

       

评论声明
  • 尊重网上道德,遵守中华人民共和国的各项有关法律法规
  • 承担一切因您的行为而直接或间接导致的民事或刑事法律责任
  • 本站管理人员有权保留或删除其管辖留言中的任意内容
  • 本站有权在网站内转载或引用您的评论
  • 参与本评论即表明您已经阅读并接受上述条款