A Space Optimized Solution of LCS | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Find lengths of two strings ; Binary index , used to index current row and previous row . ; Compute current binary index ; Last filled entry contains length of LCS for X [ 0. . n - 1 ] and Y [ 0. . m - 1 ] ; Driver code
< ? php function lcs ( $ X , $ Y ) { $ m = strlen ( $ X ) ; $ n = strlen ( $ Y ) ; $ L = array ( array ( ) ) ; for ( $ i = 0 ; $ i <= $ m ; $ i ++ ) { $ bi = $ i & 1 ; for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) { if ( $ i == 0 $ j == 0 ) $ L [ $ bi ] [ $ j ] = 0 ; else if ( $ X [ $ i - 1 ] == $ Y [ $ j - 1 ] ) $ L [ $ bi ] [ $ j ] = $ L [ 1 - $ bi ] [ $ j - 1 ] + 1 ; else $ L [ $ bi ] [ $ j ] = max ( $ L [ 1 - $ bi ] [ $ j ] , $ L [ $ bi ] [ $ j - 1 ] ) ; } } return $ L [ $ bi ] [ $ n ] ; } $ X = " AGGTAB " ; $ Y = " GXTXAYB " ; echo " Length ▁ of ▁ LCS ▁ is ▁ : ▁ " , lcs ( $ X , $ Y ) ; ? >