lintcode 求最长公共子串

2024-05-16 13:08
文章标签 最长 公共 子串 lintcode

本文主要是介绍lintcode 求最长公共子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给出两个字符串，找到最长公共子串，并返回其长度。
这个其实比较简单，因为只要返回最长公共子串的长度就可以了，不用找出他们。PS：如果要是要求返回最长公共子串呢？
动态规划，最优子结构if s[i] == t[j], L[i,j] = L[i-1,j-1]+1
if s[i]!=t[j] L[i,j] = 0, 这里是区别于最长公共子序列的，因为L[i,j] 代表以i结尾的s[i]和以j结尾的t[j]的子串的公共子串（连续）的长度，若s[i]!=s[j],则以i结尾的s[i]和以j结尾的s[j]的子串肯定不相同。
边界条件：若s ||t 为空， 一定没有公共子串;L[0,j] 和L[i,0]最多为1.

class Solution {
public:    /*** @param A, B: Two string.* @return: the length of the longest common substring.*/int longestCommonSubstring(string &A, string &B) {// write your code hereif(A.size()== 0|| B.size() == 0){return 0;}vector<vector <int>> table(A.size(), vector<int>(B.size()));int i = 0, j = 0;int length = 0;for( j = 0; j < B.size();j++){if(A[0] == B[j]){table[0][j] = 1;length = 1;}else{table[0][j] = 0;}}for (i = 0; i< A.size(); i++){if(A[i] == B[0]){table[i][0] = 1;//从内存的角度效率不高length = 1;}else{table[i][0] = 0;}}for(i = 1;i<A.size();i++){for(j = 1;j<B.size();j++){if(A[i] == B[j]){table[i][j] = table[i-1][j-1] + 1;length = table[i][j] > length? table[i][j]:length;}else{table[i][j] = 0;}}}return length;}
};

时间复杂度是O（mn），空间复杂度O(mn)，因为要申请L[m,n]个空间的数组，但是从上面
if(A[i] == B[j]){
**table[i][j] = table[i-1][j-1] + 1;**
length = table[i][j] > length? table[i][j]:length;
}else{
table[i][j] = 0;}可以看到实际计算L时只和当前行和上一行相关.也就是说进一步可以用滚动数组做。好像还可以用后缀数组做，等有时间试。

这篇关于lintcode 求最长公共子串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/994995。

相关文章

poj2406（连续重复子串）

poj2406（连续重复子串）

题意:判断串s是不是str^n，求str的最大长度。 解题思路：kmp可解，后缀数组的倍增算法超时。next[i]表示在第i位匹配失败后，自动跳转到next[i]，所以1到next[n]这个串 等于 n-next[n]+1到n这个串。 代码如下； #include<iostream>#include<algorithm>#include<stdio.h>#include<math.
阅读更多...
poj3261（可重复k次的最长子串）

poj3261（可重复k次的最长子串）

题意：可重复k次的最长子串 解题思路：求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N，但实际复杂度很低。题目数据也比较水，不然估计过不了。 代码入下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring
阅读更多...
spoj705( 求不相同的子串个数)

spoj705( 求不相同的子串个数)

题意：求串s的不同子串的个数 解题思路：任何子串都是某个后缀的前缀，对n个后缀排序，求某个后缀的前缀的个数，减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin
阅读更多...
poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...
poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大，用原来的O（n^2）会爆。 小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO
阅读更多...
hihocoder1050 : 树中的最长路

hihocoder1050 : 树中的最长路

时间限制:10000ms 单点时限:1000ms 内存限制:256MB 描述 上回说到，小Ho得到了一棵二叉树玩具，这个玩具是由小球和木棍连接起来的，而在拆拼它的过程中，小Ho发现他不仅仅可以拼凑成一棵二叉树！还可以拼凑成一棵多叉树——好吧，其实就是更为平常的树而已。 但是不管怎么说，小Ho喜爱的玩具又升级换代了，于是他更加爱不释手（其实说起来小球和木棍有什么好玩的是吧= =）。小Ho手
阅读更多...
POJ1631最长单调递增子序列

POJ1631最长单调递增子序列

最长单调递增子序列 import java.io.BufferedReader;import java.io.InputStream;import java.io.InputStreamReader;import java.io.PrintWriter;import java.math.BigInteger;import java.util.StringTokenizer;publ
阅读更多...
计蒜客 Skiing 最长路

计蒜客 Skiing 最长路

In this winter holiday, Bob has a plan for skiing at the mountain resort. This ski resort has MM different ski paths and NN different flags situated at those turning points. The ii-th path from the
阅读更多...
PHP最长单一子串

PHP最长单一子串

<?php//方法一$s='abcccddddddcdefg';$max='';while($s!=''){$i=0; while($i<strlen($s) && $s[$i]==$s[0]) $i++;if ($i>strlen($max)){$max=substr($s,0,$i);} $s=substr($s,$i);}echo $m
阅读更多...
day-50 求出最长好子序列 I

day-50 求出最长好子序列 I

思路 二维dp,dp[i][h]表示nums[i] 结尾，且有不超过 h 个下标满足条件的最长好子序列的长度（0<=h<=k），二维数组dp初始值全为1 解题过程 状态转换方程： 1.nums[i]==nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h]+1) 2.nums[i]!=nums[j],dp[i,h]=Math.max(dp[i,h],dp[j,h-1
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2