Count common subsequence in two strings | return the number of common subsequence in two strings ; for each character of S ; for each character in T ; if character are same in both the string ; Driver Code
< ? php function CommomSubsequencesCount ( $ s , $ t ) { $ n1 = strlen ( $ s ) ; $ n2 = strlen ( $ t ) ; $ dp = array ( ) ; for ( $ i = 0 ; $ i <= $ n1 ; $ i ++ ) { for ( $ j = 0 ; $ j <= $ n2 ; $ j ++ ) { $ dp [ $ i ] [ $ j ] = 0 ; } } for ( $ i = 1 ; $ i <= $ n1 ; $ i ++ ) { for ( $ j = 1 ; $ j <= $ n2 ; $ j ++ ) { if ( $ s [ $ i - 1 ] == $ t [ $ j - 1 ] ) $ dp [ $ i ] [ $ j ] = 1 + $ dp [ $ i ] [ $ j - 1 ] + $ dp [ $ i - 1 ] [ $ j ] ; else $ dp [ $ i ] [ $ j ] = $ dp [ $ i ] [ $ j - 1 ] + $ dp [ $ i - 1 ] [ $ j ] - $ dp [ $ i - 1 ] [ $ j - 1 ] ; } } return $ dp [ $ n1 ] [ $ n2 ] ; } $ s = " ajblqcpdz " ; $ t = " aefcnbtdi " ; echo CommomSubsequencesCount ( $ s , $ t ) . " " ; ? >