寻找最长公共子串_.NET_编程开发_程序员俱乐部

思想：1、对输入的两个比较字符串先构建两个字符串数组，然后根据这两个数组构建一个二维数组

　　   2、循环比较各个最小子串，如果A中某个子串与B中某个子串值一致，就执行positionArr[i,j]=1+position[i-1,j-1]操作，此处需注意边界问题

         3、标记好二维数组之后，寻找该数组中的最大值，最大值即为最长公共子串，需注意最大值的个数

         4、这种标记的思想在Matlab编程，处理微分进化算法时有相同之处，特别是求取最长基因片段，更是有异曲同工之妙。

在看《数据结构与算法》这本书的时候，发现其中对与该问题的求解程序问题漏洞太大，于是自己写了个，代码优雅性很低，读起来很好理解，希望对你有帮助。

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

namespace 最优寻找最长公共字符串
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.Write("请输入第一个字符串：");
            string firstStr = Console.ReadLine();
            Console.Write("请输入第二个字符串：");
            string secondStr = Console.ReadLine();
            string[]firstArr=new string[firstStr.Length];
            string[]secondArr=new string[secondStr.Length];
            int[,]positionArr=new int[firstArr.Length,secondArr.Length];
            SignPosition(firstStr,secondStr,firstArr,secondArr,positionArr);
            int max=FindMax(positionArr);
            ShowLongChar(max,positionArr,secondStr);
            Console.ReadKey();
        }
        /// <summary>
        /// 标记最长字符子串的位置
        /// </summary>
        /// <param name="firstWord">字符串1</param>
        /// <param name="secondWord">字符串2</param>
        /// <param name="firstArr">字符数组1</param>
        /// <param name="secondArr">字符数组2</param>
        /// <param name="positionArr">标记位置数组</param>
        static void SignPosition(string firstWord,string secondWord,string[] firstArr, string[] secondArr, int[,] positionArr)
        {
            for (int i = 0; i < firstArr.Length; i++)
            {
                firstArr[i] = firstWord.Substring(i, 1);
            }
            for (int j = 0; j < secondArr.Length; j++)
            {
                secondArr[j] = secondWord.Substring(j, 1);
            }
            for (int col = 0; col < positionArr.GetUpperBound(1) + 1; col++)
            {
                if (firstArr[0] == secondArr[col])
                {
                    positionArr[0, col] = 1;
                }
                else
                {
                    positionArr[0,col] = 0;
                }
            }
            for (int row = 1; row < positionArr.GetUpperBound(0) + 1; row++)
            {
                if (secondArr[0] == firstArr[row])
                {
                    positionArr[row, 0] = 1;
                }
                else
                {
                    positionArr[row, 0] = 0;
                }
            }
            for (int i = 1; i < positionArr.GetUpperBound(0) + 1; i++)
            {
                for (int j = 1; j < positionArr.GetUpperBound(1) + 1; j++)
                {
                    if (firstArr[i] == secondArr[j])
                    {
                        positionArr[i, j] = 1 + positionArr[i - 1, j - 1];
                    }
                    else
                    {
                        positionArr[i, j] = 0;
                    }
                }
            }
        }
        static int FindMax(int[,] positionArr)
        {
            int max = 0;
            for (int i = 0; i < positionArr.GetUpperBound(0) + 1; i++)
            {
                for (int j = 0; j < positionArr.GetUpperBound(1)+1; j++)
                {
                    if (positionArr[i, j] > max)
                    {
                        max = positionArr[i, j];
                    }
                }
            }
            return max;
        }
        static void ShowLongChar(int max,int[,]positionArr,string secondStr)
        {
            string strResult = string.Empty;
            for (int i = 0; i < positionArr.GetUpperBound(0) + 1; i++)
            {
                for (int j = 0; j < positionArr.GetUpperBound(1) + 1; j++)
                {
                    if (positionArr[i, j] == max)
                    {
                        strResult = secondStr.Substring(j-max+1, max);
                        Show(strResult);
                    }
                }
                
            }  
        }
        static void Show(string strResult)
        {
            Console.WriteLine("最长公共字符串为：" + strResult);
        }
    }
}