Dynamic Programming | Set 29 (Longest Common Substring) - GeeksforGeeks
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"
Auxiliary Space: O(m*n)
http://algods-cracker.blogspot.in/2015/04/longest-common-substring.html
int LongestCommonSubstring(std::string str1, std::string str2)
{
int len1 = str1.size(), len2 = str2.size(), max = 0;
int *curr = new int [len2], *prev = new int[len2];
for(int i = 0; i < len1; ++i)
{
for(int j = 0; j < len2; ++j)
{
if(str1[i] != str2[j])
{
curr[j] = 0;
}
else
{
if(i == 0 || j == 0)
curr[j] = 1;
else
curr[j] = 1 + prev[j-1];
}
max = max < curr[j] ? curr[j] : max;
}
int *temp = curr;
curr = prev;
prev = temp;
}
delete [] curr;
delete [] prev;
return max;
}
http://seesharpconcepts.blogspot.com/2012/08/longest-common-substring-problem.html
Also print solution:
https://karussell.wordpress.com/2011/04/14/longest-common-substring-algorithm-in-java/
The longest substring can also be solved in O(n+m) time using Suffix Tree.
http://algs4.cs.princeton.edu/63suffix/LongestCommonSubstring.java.html
Read full article from Dynamic Programming | Set 29 (Longest Common Substring) - GeeksforGeeks
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"
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
Time Complexity: O(m*n)Auxiliary Space: O(m*n)
int LCSubStr(char *X, char *Y, int m, int n){ // Create a table to store lengths of longest common suffixes of // substrings. Notethat 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[m+1][n+1]; int result = 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[i-1] == Y[j-1]) { LCSuff[i][j] = LCSuff[i-1][j-1] + 1; result = max(result, LCSuff[i][j]); } else LCSuff[i][j] = 0; } } return result;}http://algods-cracker.blogspot.in/2015/04/longest-common-substring.html
int LongestCommonSubstring(std::string str1, std::string str2)
{
int len1 = str1.size(), len2 = str2.size(), max = 0;
int *curr = new int [len2], *prev = new int[len2];
for(int i = 0; i < len1; ++i)
{
for(int j = 0; j < len2; ++j)
{
if(str1[i] != str2[j])
{
curr[j] = 0;
}
else
{
if(i == 0 || j == 0)
curr[j] = 1;
else
curr[j] = 1 + prev[j-1];
}
max = max < curr[j] ? curr[j] : max;
}
int *temp = curr;
curr = prev;
prev = temp;
}
delete [] curr;
delete [] prev;
return max;
}
http://seesharpconcepts.blogspot.com/2012/08/longest-common-substring-problem.html
Also print solution:
if str1[m] == str2[n]
LCS(Str1[1..m], str2[1..n]) = LCS(str1[1..m-1],str2[1..n-1]) +1
else
LCS(Str1[1..m], str2[1..n]) = 0
public static void PrintLongestCommonSubstring(char[] str1, char[] str2)
{
int[,] l = new int[str1.Length, str2.Length];
int lcs = -1;
string substr = string.Empty;
int end = -1;
for (int i = 0; i < str1.Length; i++)
{
for (int j = 0; j < str2.Length; j++)
{
if (str1[i] == str2[j])
{
if (i == 0 || j == 0)
{
l[i, j] = 1;
}
else
l[i, j] = l[i - 1, j - 1] + 1;
if (l[i, j] > lcs)
{
lcs = l[i, j];
end = i;
}
}
else
l[i, j] = 0;
}
}
for (int i = end - lcs + 1; i <= end; i++)
{
substr += str1[i];
}
Console.WriteLine("Longest Common SubString Length = {0}, Longest Common Substring = {1}", lcs, substr);
}
https://karussell.wordpress.com/2011/04/14/longest-common-substring-algorithm-in-java/
The longest substring can also be solved in O(n+m) time using Suffix Tree.
http://algs4.cs.princeton.edu/63suffix/LongestCommonSubstring.java.html
Read full article from Dynamic Programming | Set 29 (Longest Common Substring) - GeeksforGeeks
