关于LCS问题的研究

看了YidingHe所写的文章：《LCS问题算法VB.net版 》后很受启发，记得当年看过奥林匹克竞赛中关于某一海量位数排序的解决也是使用了类似的方法，巧妙得很。该文里面使用的二维数组转一维后使用空间确实大大降低，但也带来了一个无法同时记录多个最长匹配字符串的问题。我在看了问题描述和解决思路后，写了如下代码来探求修改，并做了NUnit测试（代码中已经省略）：

#define NTEST     // 测试控制量

using System;
using System.Diagnostics;

using NUnit.Framework;

namespace TestLCS
{
 /// <summary>
 /// Summary description for Class1.
 /// </summary>
 ///
 [TestFixture]
 public class Class1
 {
  /// <summary>
  /// The main entry point for the application.
  /// </summary>
  [STAThread]
  static void Main(string[] args)
  {
   //

   Console.Write("输入第一个字符串：");
   string strTarget1=Console.ReadLine();

   Console.Write("输入第二个字符串：");
   string strTarget2=Console.ReadLine();

   string[] astrR=MyCompare(strTarget1,strTarget2);
   Console.WriteLine ("结果是:");
   for(int i=0;i<astrR.Length;i++)
    Console.WriteLine(astrR[i]);
   Console.ReadLine();

  }

  private static void Copyaint(int[] aiImport, int[] aiOutput)
  {
   for(int i=0;i<aiImport.Length;i++)
   {
     aiOutput[i]=aiImport[i];
   }
  }

  private static string[] MyCompare(string strTarget1, string strTarget2)
  {
   string strBase,strCompare;
   // 取得最大的字符串内容
   if(strTarget1.Length>strTarget2.Length)
   { 
    strBase=strTarget1;
    strCompare=strTarget2;
   }
   else
   {
    strBase=strTarget2;
    strCompare=strTarget1;
   };

   char[] achrBase=strBase.ToCharArray();
   int[] aiResult=new int[achrBase.Length];
   int[] aiLastResult=new int[achrBase.Length];
   int[] aiFinal=new int[achrBase.Length];
   int iMax=0;  
   

   for(int iIndex=0; iIndex<strCompare.Length;iIndex++)
   {
    char chrCompare=char.Parse(strCompare.Substring(iIndex,1));
    int i=0;
    for(i=0; i<achrBase.Length; i++)
    {
     if(achrBase[i]==chrCompare)
     {
      aiResult[i]=1;     
      if(i>0 && iIndex>0 )
      {
       aiResult[i]+=aiLastResult[i-1];
      }
      
     }
     else
     {
      aiResult[i]=0;
     }
     

     if(aiResult[i]>=iMax)
     {
      iMax=aiResult[i];
      aiFinal[i]=aiResult[i];
     }
     
    }

    Copyaint(aiResult,aiLastResult);

   };

  //Console.Write("最后结果：");

  int iCount=0;
  for(int i=0; i<aiFinal.Length; i++)
  {
   if(aiFinal[i]==iMax)iCount++;
  }
  string[] astrR=new string[iCount];
  for(int i=0,j=0; i<aiFinal.Length; i++)
  {
   if(aiFinal[i]<iMax)continue;
   astrR[j]=strBase.Substring(i-aiFinal[i]+1 ,aiFinal[i]);
   j++;
  }

  return astrR;          
  }

   //
 }
}

其中，用到了两个数组（其实应该算是一个二维的（N,2）数组）来记录当前行和上一行的字符串相符信息，然后每移动到新的一行就用aiLastResult保存上一行信息，以实现连续匹配时的长度记录。不过我对这段代码不是很满意的地方是还用到了一个aiFinal来记录每行最后发现的最长匹配串。我觉得这个是应该可以优化掉的……但明天再看看有没有功夫解决吧。

 

NUnit以前用得不多，这次用感觉不错

 

本文地址：http://com.8s8s.com/it/it42553.htm