经典问题 ： 求字符串最大公共子串

求字符串最大公共子串， 要求连续，非序列

这个n^2的DP肯定也能做。总感觉能跟后缀的最长公共前缀扯上关系，但对那些知识不熟，不太确定能不能行

string findSubString(const string& a, const string& b)
{
     size_t max = 0;
     size_t maxIndex = 0;
     vector<size_t> row(b.size() + 1, 0);
     vector< vector<size_t> > dp(a.size() + 1, row);
     for (size_t i = 0; i <= b.size(); ++i)
          dp[0][i] = 0;
     for (size_t i = 0; i <= a.size(); ++i)
          dp[i][0] = 0;
     for (size_t i = 1; i <= a.size(); ++i)
          for (size_t j = 1; j <= b.size(); ++j)
          {
               if (a[i-1] == b[j-1])
               {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    if(dp[i][j] > max)
                    {
                         max = dp[i][j];
                         maxIndex = i - 1;
                    }
               }
               else
               {
                    dp[i][j] = 0;
               }
          }
     return a.substr(maxIndex - max + 1, max);
}

dp版本，应该有suffix tree版

string findSubString(const string& a, const string& b)
{
     size_t max = 0;
     size_t maxIndex = 0;
     vector row(b.size() + 1, 0);
     vector< vector > dp(a.size() + 1, row);
     for (size_t i = 0; i
Imbalism 发表于 2011-9-24 14:21

空间复杂度可以O(n)吧， 不过就是实现太麻烦了 。。。

我觉得面试时候，可以先实现n *n 的，然后再讨论下n的解法。 不用实现

回复 5# wwwyhx


    O(n)的话应该是循环数组吧。。。感觉编程上来说不太麻烦

       dp[i][j] = dp[i-1][j-1] + 1;
        变成
         dp[a][j]=dp[b][j-1]+1;
  a表示上一个状态，b表示下一个状态， 每次循环的话，可以  a=1-a b=1-b; 这样的话是开了一个2n的数组
  难道没有时间上能够达到O(n log n)的解法么。。。求教啊。。。

回复  wwwyhx


    O(n)的话应该是循环数组吧。。。感觉编程上来说不太麻烦

       dp[j] = dp[j-1] + 1;
        变成
         dp[a][j]=dp[j-1]+1;
  a表示上一个状态，b表示下一个状态， 每次循环的话，可以  a=1-a b=1-b; 这样的话是开了一个2n的数组
  难道没有时间上能够达到O(n log n)的解法么。。。求教啊。。。
ilhrx 发表于 2011-10-3 13:25

应该没有O(nlogn)的解法吧...
空间变O(n)不是说循环数组, 你看状态转移方程 : f(i, j) = str(i) == str(j) ?  f(i-1, j-1) + 1 : 0
从f(i-1, j-1) => f(i, j) 只需要上一轮计算的结果, 也就是说如果你用二维数组DP的时候,计算到第100行的时候只会用到第99行的数据, 前面1~98行的空间都浪费了, 所以用一维数组就可以了

回复 8# wwwyhx


    对。空间上的确是这么省的，所以开两个一维数组就够用了

用后缀数组：建数组O(n)，求解O(n)。。。。保证面试官都写不出来。。。