100题_20 最长公共子串

题目：如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中，则字符串一称之为字符串二的子串。注意，并不要求子串（字符串一）的字符必须连续出现在字符串二中。请编写一个函数，输入两个字符串，求它们的最长公共子串，并打印出最长公共子串。

最大公子串（LCS），其实一个比较经典的动态规划的问题。首先我们来介绍LCS问题的性质：记和为两个字符串，而，则

1. 如果，那么，并且是和的LCS；
2. 如果，那么当是，是和的LSC；
3. 如果，那么当时，是和的LCS。

上面的几个性质，基本都可以用数学归纳法来证明。有了上面的性质，我们可以得出如下的思路：求两字符串和的LCS，如果，那么只需求得和的LCS，并在其后添加（）即可；如果，我们分别求得和的LCS和和的LCS，并且这两个LCS中较长的一个为和的LCS。

如果我们记字符串和的LCS的长度为，我们可以递归地求：

上面的递归函数，如果用递归来写的话，很快就可以求得，但是直接递归会有很多的重复计算，我们可以采用保存中间结果的递归，或者采用从底向上循环求解的思路效率会更高。

下面是代码了：

#include <iostream>
#include <cstring>
#include <stack>

using namespace std;

enum Direction{Init = 0, Left, Up, LeftUp};

int lcs(const char *pa, const char *pb, char* result)
{
    if (!pa || !pb)
                return 0;
      int m = strlen(pa);
    int n = strlen(pb);
    if (!m || !n)
          return 0;
      int i, j;
      short **lcs_len = new short*[m];
     for (i = 0; i < m; i++)
     {
           lcs_len[i] = new short[n];
                for (j = 0; j < n; j++)
                     lcs_len[i][j] = 0;
  }
   short **lcs_dir = new short*[m];
     for (i = 0; i < m; i++)
     {
           lcs_dir[i] = new short[n];
                for (j = 0; j < n; j++)
                     lcs_dir[i][j] = 0;
  }

       for (i = 0; i < m; i++)
     {
           for (j = 0; j < n; j++)
             {
                   if (i == 0 || j == 0)
                  {
                           if (pa[i] == pb[j])
                            {
                                   lcs_len[i][j] = 1;
                                  lcs_dir[i][j] = LeftUp;
                             }
                           else
                                        lcs_len[i][j] = 0;
                        }
                        else if (pa[i] == pb[j])
                  {
                           lcs_len[i][j] = lcs_len[i-1][j-1] + 1;
                              lcs_dir[i][j] = LeftUp;
                     }
                   else if (lcs_len[i-1][j] > lcs_len[i][j-1])
                    {
                           lcs_len[i][j] = lcs_len[i-1][j];
                            lcs_dir[i][j] = Up;
                 }
                   else
                        {
                                lcs_len[i][j] = lcs_len[i][j-1];
                                lcs_dir[i][j] = Left;
                        }
                }
        }

        // Êä³ö½á¹û
        stack<char> myresult;
    i = m - 1;
  j = n - 1;
  while (i >= 0 && j >= 0)
 {
           if (lcs_dir[i][j] == LeftUp)
           {
                   myresult.push(pa[i]);
                       i --;
                       j --;
               }
           else if (lcs_dir[i][j] == Left)
                   i --;
               else if (lcs_dir[i][j] == Up)
                     j --;
               else
                        throw "bug";
      }
   i = 0;
      while (! myresult.empty())
     {
           result[i++] = myresult.top();
               myresult.pop();
     }
   result[i] = '\0';

       short tmp = lcs_len[m-1][n-1];

     for (i = 0; i < m; i++)
     {
           delete[] lcs_len[i];
           delete[] lcs_dir[i];
   }
   delete[] lcs_len;
      delete[] lcs_dir;

  return tmp;
}


int main()
{
       char a[] = "BDCABA";
      char b[] = "ABCBDAB";
     char result[10];
       lcs(a, b, result);
  cout<<result<<endl;
     return 0;
}