Geeks

# Description:

Given two strings ‘X’ and ‘Y’, find the length of the longest common substring.

## Example:

Input : X = "GeeksforGeeks", y = "GeeksQuiz"
Output : 5
The longest common substring is "Geeks" and is of
length 5.

Input : X = "abcdxyz", y = "xyzabcd"
Output : 4
The longest common substring is "abcd" and is of
length 4.

Input : X = "zxabcdezy", y = "yzabcdezx"
Output : 6
The longest common substring is "abcdez" and is of
length 6.

# Idea:

A simple solution is 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 (See this). So overall time complexity of this method would be O(n * m2)

Dynamic Programming can 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

time O(m n), space O(m n)

# Code:

#include <vector>
#include <iostream>
#include <string>

using namespace std;

int LCS(string s1, string s2){
if(s1.empty() || s2.empty()){
return 0;
}
int sizeS1 = s1.size();
int sizeS2 = s2.size();

vector<vector<int>> lenLCS(sizeS1+1, vector<int>(sizeS2+1, 0));
int maxLen = 0;

for(int i=0; i<sizeS1; i++){
for(int j=0; j<sizeS2; j++){
if(s1[i]==s2[j]){
lenLCS[i+1][j+1] = lenLCS[i][j] + 1;
maxLen = max(maxLen, lenLCS[i+1][j+1]);
}
}
}
return maxLen;
}

string LCSReturnString(string s1, string s2){
if(s1.empty() || s2.empty()){
return "";
}
int sizeS1 = s1.size();
int sizeS2 = s2.size();

vector<vector<int>> lenLCS(sizeS1+1, vector<int>(sizeS2+1, 0));
int maxLen = 0;
string result;
int leftIndex=0;
int rightIndex=0;

for(int i=0; i<sizeS1; i++){
for(int j=0; j<sizeS2; j++){
if(s1[i]==s2[j]){
lenLCS[i+1][j+1] = lenLCS[i][j] + 1;
if(lenLCS[i+1][j+1]>maxLen){
maxLen = lenLCS[i+1][j+1];
rightIndex=i;
leftIndex=i-maxLen+1;
}
}
}
}
return s1.substr(leftIndex, rightIndex-leftIndex+1);
}

int main(){

string s1("GeeksforGeeks");
string s2("Geeks2");

s1 = "OldSite:GeeksforGeeks.org";
s2 = "NewSite:GeeksQuiz.com";

cout<<LCS(s1, s2)<<endl;

cout<<LCSReturnString(s1, s2)<<endl;
}