Longest Common Substring | DP | Dynamic Programming solution to find length of the longest common substring ; Returns length of longest common substring of X [ 0. . m - 1 ] and Y [ 0. . n - 1 ] ; 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 ] . ; To store length of the longest common substring ; Following steps build LCSuff [ m + 1 ] [ n + 1 ] in bottom up fashion . ; Driver code
#include <iostream> NEW_LINE #include <string.h> NEW_LINE using namespace std ; int LCSubStr ( char * X , char * Y , int m , int n ) { int LCSuff [ m + 1 ] [ n + 1 ] ; int result = 0 ; 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 ; } int main ( ) { char X [ ] = " OldSite : GeeksforGeeks . org " ; char Y [ ] = " NewSite : GeeksQuiz . com " ; int m = strlen ( X ) ; int n = strlen ( Y ) ; cout << " Length ▁ of ▁ Longest ▁ Common ▁ Substring ▁ is ▁ " << LCSubStr ( X , Y , m , n ) ; return 0 ; }