数据结构（C#)-动态规划法解决两个字符串中寻觅最长公共子串
日期：2014-05-17 浏览次数：20884 次
数据结构（C#)--动态规划法解决两个字符串中寻找最长公共子串
// 实验小结 吴新强于2013年3月19日22:24:57 桂电 2507实验室
// 动态规划法解决两个字符串中寻找最长公共子串
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Chapter17_最长子串
{
class Program
{
static void Main()
{
string word1;
string word2;
Console.WriteLine("请输入字符串1： " );
word1 = Console.ReadLine();
Console.WriteLine("请输入字符串2： ");
word2 = Console.ReadLine();
string[] warray1 = new string[word1.Length];
string[] warray2 = new string[word2.Length];
string substr;
int[,] larray = new int[word1.Length, word2.Length];
LCSubstring(word1, word2, warray1, warray2, larray);
Console.WriteLine();
Console.WriteLine("两个字符串中最长公共子串比较的动态数组：");
DispArray(larray);
substr = ShowString(larray, warray1);
Console.WriteLine();
// Console.WriteLine("请输入字符串1和字符串2： " + word1 + " " + word2);
if (substr.Length > 0)
Console.WriteLine("两个字符串中最长公共子串: " + substr);
else
Console.WriteLine("两个字符串中没有最长公共子串. ");
}
static void LCSubstring(string word1, string word2, string[] warr1, string[] warr2, int[,] arr)
{
int len1, len2;
len1 = word1.Length;
len2 = word2.Length;
for (int k = 0; k <= word1.Length - 1; k++)
{
warr1[k] = word1.Substring(k, 1);
warr2[k] = word2.Substring(k, 1);
}
for (int i = len1 - 1; i >= 0; i--)
{
for (int j = len2 - 1; j >= 0; j--)
if (warr1[i] == warr2[j])
arr[i, j] = 1 + arr[i + 1, j + 1];
else
arr[i, j] = 0;
}
}
static string ShowString(int[,] arr, string[] wordArr)
{
string substr = "";
for (int i = 0; i <= arr.GetUpperBound(0);
// 实验小结 吴新强于2013年3月19日22:24:57 桂电 2507实验室
// 动态规划法解决两个字符串中寻找最长公共子串
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Chapter17_最长子串
{
class Program
{
static void Main()
{
string word1;
string word2;
Console.WriteLine("请输入字符串1： " );
word1 = Console.ReadLine();
Console.WriteLine("请输入字符串2： ");
word2 = Console.ReadLine();
string[] warray1 = new string[word1.Length];
string[] warray2 = new string[word2.Length];
string substr;
int[,] larray = new int[word1.Length, word2.Length];
LCSubstring(word1, word2, warray1, warray2, larray);
Console.WriteLine();
Console.WriteLine("两个字符串中最长公共子串比较的动态数组：");
DispArray(larray);
substr = ShowString(larray, warray1);
Console.WriteLine();
// Console.WriteLine("请输入字符串1和字符串2： " + word1 + " " + word2);
if (substr.Length > 0)
Console.WriteLine("两个字符串中最长公共子串: " + substr);
else
Console.WriteLine("两个字符串中没有最长公共子串. ");
}
static void LCSubstring(string word1, string word2, string[] warr1, string[] warr2, int[,] arr)
{
int len1, len2;
len1 = word1.Length;
len2 = word2.Length;
for (int k = 0; k <= word1.Length - 1; k++)
{
warr1[k] = word1.Substring(k, 1);
warr2[k] = word2.Substring(k, 1);
}
for (int i = len1 - 1; i >= 0; i--)
{
for (int j = len2 - 1; j >= 0; j--)
if (warr1[i] == warr2[j])
arr[i, j] = 1 + arr[i + 1, j + 1];
else
arr[i, j] = 0;
}
}
static string ShowString(int[,] arr, string[] wordArr)
{
string substr = "";
for (int i = 0; i <= arr.GetUpperBound(0);
免责声明： 本文仅代表作者个人观点，与爱易网无关。其原创性以及文中陈述文字和内容未经本站证实，对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺，请读者仅作参考，并请自行核实相关内容。
