Given two strings ‘X’ and ‘Y’, find the length of the longest common substring. For example, if the given strings are “GeeksforGeeks” and “GeeksQuiz”, the output should be 5 as longest common substring is “Geeks”
Let m and n be the lengths of first and second strings respectively.
Asimple solutionis to one by one consider all substrings of first string and for every substring check if it is a substring in second string. Keep track of the maximum length substring. There will be O(m^2) substrings and we can find whether
a string is subsring on another string in O(n) time (Seethis). So overall time complexity
of this method would be O(n * m2)
Dynamic Programmingcan be used to find the longest common substring in O(m*n) time. The idea is to find length of the longest common suffix for all substrings of both strings and store these lengths in a table.
The longest common suffix has following optimal substructure property
LCSuff(X, Y, m, n) = LCSuff(X, Y, m-1, n-1) + 1 if X[m-1] = Y[n-1]
0 Otherwise (if X[m-1] != Y[n-1])
The maximum length Longest Common Suffix is the longest common substring.
LCSubStr(X, Y, m, n) = Max(LCSuff(X, Y, i, j)) where 1 <= i <= m
and 1 <= j <= n
The longest substring can also be solved in O(n+m) time using Suffix Tree. We will be covering Suffix Tree based solution in a separate post.
思路:
1 暴力枚举 O(m^2 * n):在长度为m的string里枚举所有子串需要O(m^2),对于每一个子串要在另一个长度为n的string里找相同,用KMP需要O(n)
2 DP 把求相同子串的问题转为求相同后缀的问题 O(m*n)
3 后缀树: O(m+n)
参考https://en.wikipedia.org/wiki/Longest_common_substring_problem
DP:
package DP;
public class LongestCommonSubstring {
public static void main(String[] args) {
String X = "OldSite:GeeksforGeeks.org";
String Y = "NewSite:GeeksQuiz.com";
int m = X.length();
int n = Y.length();
System.out.println(LCSubstr(X, Y, m, n));
}
// Time Complexity: O(m*n) Time Complexity: O(m*n)
public static int LCSubstr(String X, String Y, int m, int n) {
// Create a table to store lengths of longest common suffixes of
// substrings. Note that LCSuff[i][j] contains length of longest
// common suffix of X[0..i-1] and Y[0..j-1]. The first row and
// first column entries have no logical meaning, they are used only
// for simplicity of program
int[][] LCSuff = new int[m + 1][n + 1];
int longest = 0;
// To store length of the longest common substring
/* Following steps build LCSuff[m+1][n+1] in bottom up fashion. */
for (int i = 0; i <= m; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0 || j == 0) {
LCSuff[i][j] = 0;
} else if (X.charAt(i - 1) == Y.charAt(j - 1)) {
LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;
longest = Math.max(longest, LCSuff[i][j]);
} else {
LCSuff[i][j] = 0;
}
}
}
return longest;
}
}
http://www.geeksforgeeks.org/longest-common-substring/
分享到:
相关推荐
LCS(longest common substring)算法,即最大公共子串,它是求两个字符串最长公共子串的问题。大体解法是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长...
7-6 最长对称子串 (25分) 对给定的字符串,本题要求你输出最长对称子串的长度。例如,给定Is PAT&TAP symmetric?,最长对称子串为s PAT&TAP s,于是你应该输出11。 输入格式: 输入在一行中给出长度不超过1000的...
【问题描述】 在随意给出的2个字符串中,找出它们共同的最长的子串。...输出只有一行,即:共同的最长子串,若有多个不同的最长子串(即长度相同),输出任意一个。 文件的输入为文件input.txt,输出为标准输出
最长公共子串的快速搜索算法 最长公共子串的快速搜索算法 最长公共子串的快速搜索算法
输入一个字符串,求出其中最长的回文子串。子串的含义是:在原串中连续出现的字符串片段。回文的含义是:正着看和倒着看相同,如abba和xyyxyyx。在判断时,应该忽略所有标点符号和空格,且忽略大小写,但输出应该...
最长回文子串
最长公共子串求解,有需要的可以下来参考……
最长公用子串LCS服务器 最长公共子字符串(LCS)服务器概述构建一个简单的Web应用程序,允许用户在给定字符串列表的情况下请求最长公共子字符串。 功能要求通过HTTP POST解决最长的公共子字符串问题用户应该能够通过...
查找两个字符串a,b中的最长的公共子串,并将结果输出
本文实例讲述了C语言求两个字符串的最长公共子串的方法。分享给大家供大家参考。具体实现方法如下: #include "stdio.h" #include "string.h" #include "stdlib.h" void getCommon(char str1[],char str2[],char * ...
最长回文子串,算法还算可以,能运行通过,运行时间也不长
最长公共子串(LongestCommonSubstring)是一个非常经典的面试题目,在实际的程序中也有很高的实用价值,所以把该问题的解法总结在本文重。不过不单单只是写出该问题的基本解决代码而已,关键还是享受把学习算法一步步...
最长回文子串(dp)1
大整数计算器最长公共子串数据结构课设,沈阳工程学院
用定长顺序存储结构表示串: (1) 建立两个文本文件,分别存储串str1“hellohisgoodl”和串str“hellogdygoodl” (2) 输出两个串的最长公共子串“hello”和“goodl”; (3) 分析算法时间复杂度。
最长公共子串(The Longest Common Substring) LCS问题就是求两个字符串最长公共子串的问题。解法就是用一个矩阵来记录两个字符串中所有位置的两个字符之间的匹配情况,若是匹配则为1,否则为0。然后求出对角线最长的1...
求解最大子序列、最长递增子序列、最长公共子串、最长公共子序列. http://blog.csdn.net/ssuchange/article/details/17341693
求两个字符数组的最长公共子串的问题,使用动态规划法,java语言实现。
题目:如果字符串一的所有字符... 分析:求最长公共子串(Longest Common Subsequence, LCS)是一道非常经典的动态规划题,因此一些重视算法的公司像MicroStrategy都把它当作面试题。完整介绍动态规划将需要很长的篇幅
动态规划:最长公共子串 LCS 动态规划:最长公共子串 LCS