day11

Day 11 - Longest Common Substring

Question -- Given two strings, write a program to find the longest string that is a substring of both the given strings.

Example

input: str1 = "abcdefg", str2 = "xyabcz"
output: "abc"
input: str1 = "XYXYXYZ", str2 = "XYZYX"
output: "XYZ"

Illustration from Wikipedia

The longest common substring of the strings "ABABC", "BABCA" and "ABCBA" is string "ABC" of length 3. Other common substrings are "A", "AB", "B", "BA", "BC" and "C".

 ABABC
|||
BABCA
|||
ABCBA

JavaScript Implementation

Solution using dynamic programming

Reference -- Wikipedia

/** * @author MadhavBahl * @date 03/01/2018 * Referance: https://en.wikipedia.org/wiki/Longest_common_substring_problem */functionlongestSubstring(str1,str2){// initialize the longest substring matrix with all zeroesletstrMat=[],len1=str1.length,len2=str2.length;for(leti=0;i<=len2;i++){letrow=[];for(letj=0;j<=len1;j++){row.push(0);}strMat.push(row);}// Fill the longest substring matrix and find the maximum element simultaneouslyletmaxi=0,maxj=0,max=strMat[0][0];for(leti=1;i<=len2;i++){for(letj=1;j<=len1;j++){if(str2[i-1]===str1[j-1]){strMat[i][j]=strMat[i-1][j-1]+1;if(strMat[i][j]>max){max=strMat[i][j];maxi=i;maxj=j;}}}}// Find the longest substringletmaxSubStr='';for(i=maxi,j=maxj;i>=0;i--,j--){if(!(i<=0||j<=0)&&strMat[i][j]!==0){maxSubStr+=str2[i-1];}else{break;}}// Return the reverse of maxSubStrreturnmaxSubStr.split('').reverse().join('');}console.log(longestSubstring("abcdefg","xyabcz"));console.log(longestSubstring("XYXYXYZ","XYZYX"));

C++ Implementation

Solution using dynamic programming

/** * @author:divyakhetan * @date: 3/1/2019*/
#include<bits/stdc++.h>usingnamespacestd;intmain() {
string s1,s2;
cin >> s1 >> s2;
int n = s1.length();
int m = s2.length();
int lcs[n + 1][m + 1];
int ma = 0;
int mi = 0;
int mj = 0;
for(int i =0; i <=n; i++){
for(int j = 0; j <=m;j++){
if(i == 0 || j == 0) lcs[i][j] = 0;
elseif(s1[i -1] == s2[j - 1]){
lcs[i][j] = 1 + lcs[i - 1][j - 1];
if(lcs[i][j] > ma){
mi = i;
mj = j;
ma = lcs[i][j];
}
}
else{
lcs[i][j]= 0;
}
}
}
int i = 0;
int j = 0;
string ans= "";
for (i=mi, j=mj; i>=0; i--, j--) {
if (!(i<=0 || j<=0) && lcs[i][j] != 0) {
ans += s1[i-1];
} else {
break;
}
}
reverse(ans.begin(), ans.end());
cout << "len : " << ma << " is " << ans;
}

Solution by @imkaka

/** @author : imkaka* @date : 04/01/2019*/
#include<iostream>
#include<string>usingnamespacestd;voidlongestCommonSubstrig(string, string);
intmain(){
string str1 = "bisect", str2 = "secret";
longestCommonSubstrig(str1, str2); // seclongestCommonSubstrig("abcxyzey", "cxyazeal"); //cxyreturn0;
}
voidlongestCommonSubstrig(string str1, string str2){
int m = str1.size();
int n = str2.size();
intLCW[m+1][n+1];
//Track Len and location.int maxLCW = 0;
int loc = m+1;
for(int i = 0; i <= m; ++i){
LCW[i][n] = 0;
}
for(int i = 0; i <= n; ++i){
LCW[m][i] = 0;
}
// Calculating the max length of common subwordfor(int c = n-1; c >= 0; --c){
for(int r = m-1; r >= 0; --r){
if(str1[r] == str2[c]){
LCW[r][c] = 1 + LCW[r+1][c+1];
}
else{
LCW[r][c] = 0;
}
if(LCW[r][c] > maxLCW){
maxLCW = LCW[r][c];
loc = r;
}
}
}
// Finding the Common SubWord
string re = "";
for(int r = loc; r < loc + maxLCW; ++r){
re += char(str1[r]);
}
cout << re << endl;
}

Java Implementation

Solution

/** * @date 03/01/1998 * @author SPREEHA DUTTA */importjava.util.*;
publicclasslongestCommonSubstring {
staticintmax=0;staticStringsm;
publicstaticvoidgenerate(Strings,Stringst)
{
Stringstr;
for(inti=0;i<=s.length()-1;i++)
{
for(intj=i+1;j<=s.length();j++)
{
str=s.substring(i,j);
if(st.contains(str))
{
if(max<str.length())
{
max=str.length();
sm=str;
}
}
}
}
}
publicstaticvoidmain(String []args)
{
Scannersc=newScanner(System.in);
Strings1,s2;
System.out.println("Enter the two strings ");
s1=sc.next();
s2=sc.next();
generate(s1,s2);
generate(s2,s1);
System.out.println("Longest common substring is "+sm);
}
}

Python Implementation

Solution using dynamic programming

""" @author : vishalshirke7 @date : 03/01/2019"""deflcs(str1, str2):
m, n=len(str1), len(str2)
L= [[0foryinrange(n+1)] forxinrange(m+1)]
foriinrange(m+1):
forjinrange(n+1):
ifi==0orj==0:
L[i][j] =0elifstr1[i-1] ==str2[j-1]:
L[i][j] =L[i-1][j-1] +1else:
L[i][j] =max(L[i-1][j], L[i][j-1])
index=L[m][n]
# Create a character array to store the lcs stringlcs_str= [""] * (index+1)
lcs_str[index] =""# Start from the right-most-bottom-most corner and# one by one store characters in lcs[]i=mj=nwhilei>0andj>0:
# If current character in X[] and Y are same, then# current character is part of LCSifstr1[i-1] ==str2[j-1]:
lcs_str[index-1] =str1[i-1]
i-=1j-=1index-=1# If not same, then find the larger of two and# go in the direction of larger valueelifL[i-1][j] >L[i][j-1]:
i-=1else:
j-=1print("LCS of "+str1+" and "+str2+" is -"+"".join(lcs_str))
lcs(*(input().split()))

Solution 2

'''@author: aaditkamat@date: 03/01/2019'''defprint_output(str1, str2):
print(f'The longest common substring in {str1} and {str2} is: {longest_common_substring(str1, str2)}')
defsubstrings(string):
lst= []
n=len(string)
foriinrange(1, n+1):
forjinrange(n+1-i):
lst.append(string[j : j+i])
print(set(lst))
returnset(lst)
deflongest_common_substring(str1, str2):
str1_substrings=substrings(str1)
str2_substrings=substrings(str2)
common_substrings=str1_substrings&str2_substringsiflen(common_substrings) ==0:
common_substrings.add("")
returnmax(common_substrings, key=lambdax: len(x))
print_output("abcdefg", "xyabcz")
print_output("XYXYXYZ", "XYZYX")
print_output("abcd", "efgh")