江苏龙网

  1. 首页 > 人文 > >

算法|算法：最大公共子串

吒吒，你知道怎么求两个字符串的最大公共子串吗？
不知道呀，怎么了，丙丙？
这道题可是在牛客网上热门算法题中成功率最低的一道题之一，好像只有不到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]？


推荐阅读


上一篇： 聊城市|聊城市护国隆兴寺复建中轴线殿堂建筑启用暨2021新年祈福法会

下一篇： 忍让|忍让，若是没有底线便成为负担