# Longest common substring problem

### Write a program to find the longest common sub-string of two given strings

The approach:-

1. Key to the LCS problem is to generate a LCS matrix based on which the longest common sub-string could be derived.
2. There is a cool video explaining the LCS matrix construction from Jay Liew, Security Researcher @ Websense Security Labs.

The solution:-

`#include <iostream>#include <cstdlib>using namespace std;int main() {char input1[] = "philologist";char input2[] = "lollipop";int sz1 = sizeof(input1) / sizeof(char);int sz2 = sizeof(input2) / sizeof(char);sz1--;sz2--;cout << "Input strings" << endl;cout << "-------------" << endl;cout << input1 << endl;cout << input2 << endl;cout << endl;int max_sz = 0;int max_index = 0;char* out = (char*) malloc(min(sz1, sz2) + 1);int ** matrix = (int**)calloc(sizeof(int), sz1 + 1);for ( int i = 0; i < sz1 + 1; i++ )matrix[i] = (int*)calloc(sizeof(int), sz2 + 1);char* ptr1 = input1;char* ptr2 = input2;for ( int i = 0; i < sz1; i++ ) {for ( int j = 0; j < sz2; j++ ) {if ( input1[i] == input2[j] ) {int val = matrix[i][j] + 1;matrix[i+1][j+1] = val;if ( val > max_sz ) {max_sz = val;max_index = j;}}}}cout << "LCS matrix" << endl;cout << "----------" << endl;for ( int i = 0; i < sz1 + 1; i++ ) {for ( int j = 0; j < sz2 + 1; j++ ) {cout << matrix[i][j] << " ";}cout << endl;}cout << "Maximum size of substring = " << max_sz << endl;cout << "Maximum size of substring ends at index = " << max_index << endl;cout << "Longest common substring = ";for ( int i = max_index - max_sz + 1; i <= max_index; i++ )cout << input2[i];cout << endl;}`

Output:-

`Input strings-------------philologistlollipopLCS matrix----------0 0 0 0 0 0 0 0 00 0 0 0 0 0 1 0 10 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 00 1 0 1 1 0 0 0 00 0 2 0 0 0 0 1 00 1 0 3 1 0 0 0 00 0 2 0 0 0 0 1 00 0 0 0 0 0 0 0 00 0 0 0 0 1 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0Maximum size of substring = 3Maximum size of substring ends at index = 2Longest common substring = lol`