Edit distance and LCS ( Longest Common Subsequence ) | PHP program to find Edit Distance ( when only two operations are allowed , insert and delete ) using LCS . ; Find LCS ; Edit distance is delete operations + insert operations . ; Driver Code
< ? php function editDistanceWith2Ops ( $ X , $ Y ) { $ m = strlen ( $ X ) ; $ n = strlen ( $ Y ) ; $ L [ $ m + 1 ] [ $ n + 1 ] ; 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 ] ) ; } } $ lcs = $ L [ $ m ] [ $ n ] ; return ( $ m - $ lcs ) + ( $ n - $ lcs ) ; } $ X = " abc " ; $ Y = " acd " ; echo editDistanceWith2Ops ( $ X , $ Y ) ; ? >