Minimum Cost To Make Two Strings Identical | Returns length of LCS for X [ 0. . m - 1 ] , Y [ 0. . n - 1 ] ; Following steps build L [ m + 1 ] [ n + 1 ] in bottom up fashion . Note that L [ i ] [ j ] contains length of LCS of X [ 0. . i - 1 ] and Y [ 0. . j - 1 ] ; L [ m ] [ n ] contains length of LCS for X [ 0. . n - 1 ] and Y [ 0. . m - 1 ] ; Returns cost of making X [ ] and Y [ ] identical . costX is cost of removing a character from X [ ] and costY is cost of removing a character from Y [ ] / ; Find LCS of X [ ] and Y [ ] ; Cost of making two strings identical is SUM of following two 1 ) Cost of removing extra characters from first string 2 ) Cost of removing extra characters from second string ; Driver program to test above function
< ? php function lcs ( $ X , $ Y , $ m , $ n ) { $ L = array_fill ( 0 , ( $ m + 1 ) , array_fill ( 0 , ( $ n + 1 ) , NULL ) ) ; for ( $ i = 0 ; $ i <= $ m ; $ i ++ ) { for ( $ j = 0 ; $ j <= $ n ; $ j ++ ) { if ( $ i == 0 $ j == 0 ) $ L [ $ i ] [ $ j ] = 0 ; else if ( $ X [ $ i - 1 ] == $ Y [ $ j - 1 ] ) $ L [ $ i ] [ $ j ] = $ L [ $ i - 1 ] [ $ j - 1 ] + 1 ; else $ L [ $ i ] [ $ j ] = max ( $ L [ $ i - 1 ] [ $ j ] , $ L [ $ i ] [ $ j - 1 ] ) ; } } return $ L [ $ m ] [ $ n ] ; } function findMinCost ( & $ X , & $ Y , $ costX , $ costY ) { $ m = strlen ( $ X ) ; $ n = strlen ( $ Y ) ; $ len_LCS = lcs ( $ X , $ Y , $ m , $ n ) ; return $ costX * ( $ m - $ len_LCS ) + $ costY * ( $ n - $ len_LCS ) ; } $ X = " ef " ; $ Y = " gh " ; echo " Minimum ▁ Cost ▁ to ▁ make ▁ two ▁ strings ▁ " . " identical is = " return 0 ; ? >