Longest Common Substring | DP | 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 the 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 the program . ; To store the length of longest common substring ; Following steps to build LCSuff [ m + 1 ] [ n + 1 ] in bottom up fashion ; Driver Code
def LCSubStr ( X , Y , m , n ) : NEW_LINE INDENT LCSuff = [ [ 0 for k in range ( n + 1 ) ] for l in range ( m + 1 ) ] NEW_LINE result = 0 NEW_LINE for i in range ( m + 1 ) : NEW_LINE INDENT for j in range ( n + 1 ) : NEW_LINE INDENT if ( i == 0 or j == 0 ) : NEW_LINE INDENT LCSuff [ i ] [ j ] = 0 NEW_LINE DEDENT elif ( X [ i - 1 ] == Y [ j - 1 ] ) : NEW_LINE INDENT LCSuff [ i ] [ j ] = LCSuff [ i - 1 ] [ j - 1 ] + 1 NEW_LINE result = max ( result , LCSuff [ i ] [ j ] ) NEW_LINE DEDENT else : NEW_LINE INDENT LCSuff [ i ] [ j ] = 0 NEW_LINE DEDENT DEDENT DEDENT return result NEW_LINE DEDENT X = ' OldSite : GeeksforGeeks . org ' NEW_LINE Y = ' NewSite : GeeksQuiz . com ' NEW_LINE m = len ( X ) NEW_LINE n = len ( Y ) NEW_LINE print ( ' Length ▁ of ▁ Longest ▁ Common ▁ Substring ▁ is ' , LCSubStr ( X , Y , m , n ) ) NEW_LINE