从优化到再优化，最长公共子串_广义后缀树资源-CSDN文库

30 浏览量 2021-02-03 05:54:27 上传评论收藏 473KB PDF 举报

资源推荐

资源详情

资源评论

从优化到再优化，最长公共子串从优化到再优化，最长公共子串

最长公共子串(Longest Common Substring)是一个非常经典的面试题目，在实际的程序中也有很高的实用价值，所以把该问题

的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已，关键还是享受把学习算法一步步的优化，让时间和空

间复杂度一步步的减少的惊喜。

概览

最长公共子串问题的基本表述为：

给定两个字符串，求出它们之间最长的相同子字符串的长度。

最直接的解法自然是找出两个字符串的所有子字符串进行比较看他们是否相同，然后取得相同最长的那个。对于一个长度为n的

字符串，它有n(n+1)/2 个非空子串。所以假如两个字符串的长度同为n，通过比较各个子串其算法复杂度大致为O(n4)。这还没

有考虑字符串比较所需的时间。简单想想其实并不需要取出所有的子串，而只要考虑每个子串的开始位置就可以，这样可以把

复杂度减到O(n3)。

但这个问题最好的解决办法是动态规划法，在后边会更加详细介绍这个问题使用动态规划法的契机：有重叠的子问题。进而可

以通过空间换时间，让复杂度优化到O(n2)，代价是空间复杂度从O(1)一下子提到了O(n2)。

从时间复杂度的角度讲，对于最长公共子串问题，O(n2)已经是目前我所知最优的了，也是面试时所期望达到的。但是对于空间

复杂度O(n2)并不算什么，毕竟算法上时间比空间更重要，但是如果可以省下一些空间那这个算法就会变得更加美好。所以进一

步的可以把空间复杂度减少到O(n)，这是相当美好了。但有一天无意间让我发现了一个算法可以让该问题的空间复杂度减少回

原来的O(1)，而时间上如果幸运还可以等于O(n)。

暴力解法 – 所得即所求

对于该问题，直观的思路就是问题要求什么就找出什么。要子串，就找子串；要相同，就比较每个字符；要最长就记录最长。

所以很容易就可以想到如下的解法。

int longestCommonSubstring_n3(const string& str1, const string& str2)

{

size_t size1 = str1.size();

size_t size2 = str2.size();

if (size1 == 0 || size2 == 0) return 0;

// the start position of substring in original string

int start1 = -1;

int start2 = -1;

// the longest length of common substring

int longest = 0;

// record how many comparisons the solution did;

// it can be used to know which algorithm is better

int comparisons = 0;

for (int i = 0; i < size1; ++i)

{

for (int j = 0; j < size2; ++j)

{

// find longest length of prefix

int length = 0;

int m = i;

int n = j;

while(m < size1 && n < size2)

{

++comparisons;

if (str1[m] != str2[n]) break;

++length;

++m;

++n;

}

if (longest < length)

{

longest = length;

start1 = i;

start2 = j;

}

#ifdef IDER_DEBUG

cout<< "(first, second, comparisions) = ("

<< start1 << ", " << start2 << ", " << comparisons

<< ")" << endl;

#endif

return longest;

}

该解法的思路就如前所说，以字符串中的每个字符作为子串的端点，判定以此为开始的子串的相同字符最长能达到的长度。其

实从表层上想，这个算法的复杂度应该只有O(n2)因为该算法把每个字符都成对相互比较一遍，但关键问题在于比较两个字符串

的效率并非是O(1)，这也导致了实际的时间复杂度应该是满足Ω(n2)和O(n3)。

动态规划法 – 空间换时间

有了一个解决问题的方法是一件很不错的事情了，但是拿着上边的解法回答面试题肯定不会得到许可，面试官还是会问有没有

更好的解法呢？不过上述解法虽然不是最优的，但是依然可以从中找到一个改进的线索。不难发现在子串比较中有很多次重复

的比较。

比如再比较以i和j分别为起始点字符串时，有可能会进行i+1和j+1以及i+2和j+2位置的字符的比较；而在比较i+1和j+1分别为起

始点字符串时，这些字符又会被比较一次了。也就是说该问题有非常相似的子问题，而子问题之间又有重叠，这就给动态规划

法的应该提供了契机。

暴力解法是从字符串开端开始找寻，现在换个思维考虑以字符结尾的子串来利用动态规划法。

假设两个字符串分别为s和t，s[i]和t[j]分别表示其第i和第j个字符(字符顺序从0开始)，再令L[i, j]表示以s[i]和s[j]为结尾的相同子串

的最大长度。应该不难递推出L[i, j]和L[i+1,j+1]之间的关系，因为两者其实只差s[i+1]和t[j+1]这一对字符。若s[i+1]和t[j+1]不同，

那么L[i+1, j+1]自然应该是0，因为任何以它们为结尾的子串都不可能完全相同；而如果s[i+1]和t[j+1]相同，那么就只要在以s[i]

和t[j]结尾的最长相同子串之后分别添上这两个字符即可，这样就可以让长度增加一位。合并上述两种情况，也就得到

L[i+1,j+1]=(s[i]==t[j]?L[i,j]+1:0)这样的关系。

最后就是要小心的就是临界位置：如若两个字符串中任何一个是空串，那么最长公共子串的长度只能是0；当i为0时，L[0,j]应该

是等于L[-1,j-1]再加上s[0]和t[j]提供的值，但L[-1,j-1]本是无效，但可以视s[-1]是空字符也就变成了前面一种临界情况，这样就可

知L[-1,j-1]==0，所以L[0,j]=(s[0]==t[j]?1:0)。对于j为0也是一样的，同样可得L[i,0]=(s[i]==t[0]?1:0)。

最后的算法代码如下：

剩余8页未读，继续阅读

评论收藏

内容反馈

weixin_38625164

粉丝: 4
资源: 910

从优化到再优化，最长公共子串

输入两个字符串，求它们最长公共字串的长度

JavaScript实现求最大公共子串的方法

最长公共子串（动态规划）1

C语言求两个字符串的最长公共子串

详解Python最长公共子串和最长公共子序列的实现

获取最长公共子串

最长公共子串的快速搜索算法

Python最长公共子串算法实例

PHP实现求解最长公共子串问题的方法

动态规划：最长公共子串 LCS

查找最长公共子串

最长公共子串MFC实现

最长公共子串的求解问题

python实现求两个字符串的最长公共子串方法

输出最长子串的代码

求两个字符串的最长公共字串。

Python求两个字符串最长公共子序列代码实例

新建 WinRAR 压缩文件_最长公共子串_

PHP实现求两个字符串最长公共子串的方法示例

求最长的公共子串

LCS最长公共子串

C#最长公共子串(连续)算法(自创)

最长公共子串

C++实现找出两个字符串中最大的公共子串

最新资源