算法：最大公共子串

吒吒，你知道怎么求两个字符串的最大公共子串吗？

不知道呀，怎么了，丙丙？

这道题可是在牛客网上热门算法题中成功率最低的一道题之一，好像只有不到10%的正确率哦。但是却一直是考的最多的几道题之一。

啊，那一定很难吧？而且我也要找工作了呢，我还不会这个呀。

一点都不难，我就会好几种解法呢，我来教你吧。

好啊好啊，你真好，丙丙。

吒吒，请听题：

给定两个字符串str1和str2,输出两个字符串的最长公共子串，如果最长公共子串为空，输出-1。

比如："ab123cd"，"a123456c"，

返回："123"，

备注：1≤|str1|,|str2|≤5000

嗯... ...是不是可以直接用两层嵌套循环遍历啊？

bingo，答对了。这可能是大部分人的第一反应。

我这里有张图你先给你看看吧。

嗯好的。

我明白了！

我们str1取一个i作为索引值，二层循环中str2取j作为索引值。

当str1[i]==str2[j]时，分别使用临时索引m=i，n=j，临时指针m与n，同时往后+1，直到str1[m]与str2[n]不同。

嗯，说的不错，还有呢？

这样，以str[i]为起点的公共最长子串长度为m-i，子串在str1的起点为str[i]。

在遍历中可以取一个maxLength作为最大长度保存值，maxEndIndexInArray1作为子序列的终点在str1的索引值。

当出现某个点超出点长度大于maxLengthn时，则更新maxLength与maxEndIndexInArray1。

嗯，可以可以，孺子可教。

我代码写好了你看看有什么问题吗？

没啥问题，但是务必记得加上下标范围的约束， 避免下标越界， 很多人就失败在这里。

嗯嗯！

这种是暴力解法，虽然思路简单明了。

两层循环，设定m、n分别是字符串长度的话，最大长度maxLenth，时间复杂度为O(m * n * maxLength)，空间复杂度是O(1)。

还是可以继续优化的。

我还没有思路额。

你听我说。

对于str1中每个元素，都循环一次str2中所有元素有点浪费。

可以用str2的元素集合构建一个map，key是元素值，value是元素的index。

考虑到可能多个index同样的值，value可以设置为多个index用逗号分隔的字符串。

这样以str1元素为驱动元素的话，只需要在map中找是否有对应的元素，有的话取出他们在str2中的索引列表。

啊，我知道了。

然后针对每个index用上面的图示的双临时指针计算最大子串。

这样的话，时间复杂度为O(m * maxLength)，但是空间复杂度由于引入了map，增加为O(n)。

这样好处就可以通过map直接定位元素在str2中位置，不必循环比较str2中元素。

你看我代码。

对！但是其实上面的两种解法都能实现功能，但是有个浪费点在于。

在多轮嵌套循环中，可能有很多重复比较值。

比如在i=1，j=2 时比较了 str1[4] 与 str2[5] 是否相等，而在 i=2，j=3 时可能会再次需要比较 str1[4] 与 str2[5] 是否相同。

对哦，那怎么办才好呢？

你想下，我们是不是可以考虑用一个二维素组dp [m+1] [n+1]来保存 str1[m] 与 str2[n] 是否相同的信息？

如果 str1[m]!=str2[n]，dp[m+1] [n+1]=0 标识他们不相等。

如果str1[m]==str2[n]，dp[m+1] [n+1]则不为0，标识他们相等。

同时这个点值存放的是dp[m+1] [n+1]点即str1[m]与str2[n]点已经达到的公共子串长度。

那为什么要用dp[m+1] [n+1]保存str1[m]，str2[n]是否相等信息，而不用dp[m] [n]？

这是因为如果str1[m]==str2[n]，dp[m+1] [n+1]=dp[m] [n]+1，而对于str1中m为0，str2中n为0时，如果用dp[0] [0]来保存，则没有dp[-1] [-1]的元素（数组元素下标最小为0）。

因此都是用dp[m+1] [n+1]来标识str1[m]，str2[n]是否相等信息。

哦，好像是这样的哦，可是我还是有点迷糊。

没事儿，我画了张，你对照图看就能明白了。

代码实现如下：

你学会了吗，吒吒？

嗯，我看懂了哦，原来这么容易啊。

那你来总结下几种解法有什么区别吧？

嗯，第三种解法采取了动态规划的思想，解决的问题多数有重叠子问题这个特点，为了减少重复计算，对每一个子问题只解一次，将其不同阶段的不同状态保存在一个二维数组中。

这样的话，复杂度就是O(m * n)，空间复杂度O(m * n)。

通过用空间换时间，使得字符串1与字符串2每个只是比较了一次！

那他和第一种、第二种解法又有什么不同呢？

他的执行效率优于第一种解法，而和第二种基于map定位的算法各有优劣。

当字符串重复率不高时而长度较长时，第二种算法（hash定位）时间和空间都优于第三种（动态规划）的算法。

当字符串中重复率逐渐升高时，第二种hash的算法效率明显下降，这时候，采用动态规划效率就更高。

不错啊，看来你完全掌握了哦，下次再教你一点新东西吧。

还是丙丙你教的好啊。好啊，下次我们再约！