LCS ( Longest Common Subsequence ) of three strings | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] and Z [ 0. . o - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] [ o + 1 ] in bottom up fashion . Note that L [ i ] [ j ] [ k ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] and Z [ 0. . ... k - 1 ] ; L [ m ] [ n ] [ o ] contains length of LCS for X [ 0. . n - 1 ] and Y [ 0. . m - 1 ] and Z [ 0. . o - 1 ] ; Driver code
< ? php function lcsOf3 ( $ X , $ Y , $ Z , $ m , $ n , $ o ) { $ L [ $ m + 1 ] [ $ n + 1 ] [ $ o + 1 ] = array ( array ( array ( ) ) ) ; for ( $ i = 0 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) { for ( $ k = 0 ; $ k <= $ o ; $ k ++ ) { if ( $ i == 0 $ j == 0 $ k == 0 ) $ L [ $ i ] [ $ j ] [ $ k ] = 0 ; else if ( $ X [ $ i - 1 ] == $ Y [ $ j - 1 ] && $ X [ $ i - 1 ] == $ Z [ $ k - 1 ] ) $ L [ $ i ] [ $ j ] [ $ k ] = $ L [ $ i - 1 ] [ $ j - 1 ] [ $ k - 1 ] + 1 ; else $ L [ $ i ] [ $ j ] [ $ k ] = max ( max ( $ L [ $ i - 1 ] [ $ j ] [ $ k ] , $ L [ $ i ] [ $ j - 1 ] [ $ k ] ) , $ L [ $ i ] [ $ j ] [ $ k - 1 ] ) ; } } } return $ L [ $ m ] [ $ n ] [ $ o ] ; } $ X = " AGGT12" ; $ Y = "12TXAYB " ; $ Z = "12XBA " ; $ m = strlen ( $ X ) ; $ n = strlen ( $ Y ) ; $ o = strlen ( $ Z ) ; echo " Length ▁ of ▁ LCS ▁ is ▁ " . lcsOf3 ( $ X , $ Y , $ Z , $ m , $ n , $ o ) ; ? >