Number of ways to insert a character to increase the LCS by one | JavaScript Program for Number of ways to insert a character to increase LCS by one ; Return the Number of ways to insert a character to increase the Longest Common Subsequence by one ; Insert all positions of all characters in string B . ; Longest Common Subsequence ; Longest Common Subsequence from reverse ; inserting character between position i and i + 1 ; Driver Code
let MAX = 256 ; function numberofways ( A , B , N , M ) { let pos = new Array ( MAX ) ; for ( let i = 0 ; i < MAX ; i ++ ) pos [ i ] = [ ] ; for ( let i = 0 ; i < M ; i ++ ) pos [ B [ i ] . charCodeAt ( 0 ) ] . push ( i + 1 ) ; let dpl = new Array ( N + 2 ) ; for ( let i = 0 ; i < N + 2 ; i ++ ) { dpl [ i ] = new Array ( M + 2 ) ; for ( let j = 0 ; j < M + 2 ; j ++ ) dpl [ i ] [ j ] = 0 ; } for ( let i = 1 ; i <= N ; i ++ ) { for ( let j = 1 ; j <= M ; j ++ ) { if ( A [ i - 1 ] == B [ j - 1 ] ) dpl [ i ] [ j ] = dpl [ i - 1 ] [ j - 1 ] + 1 ; else dpl [ i ] [ j ] = Math . max ( dpl [ i - 1 ] [ j ] , dpl [ i ] [ j - 1 ] ) ; } } let LCS = dpl [ N ] [ M ] ; let dpr = new Array ( N + 2 ) ; for ( let i = 0 ; i < N + 2 ; i ++ ) { dpr [ i ] = new Array ( M + 2 ) ; for ( let j = 0 ; j < M + 2 ; j ++ ) dpr [ i ] [ j ] = 0 ; } for ( let i = N ; i >= 1 ; i -- ) { for ( let j = M ; j >= 1 ; j -- ) { if ( A [ i - 1 ] == B [ j - 1 ] ) dpr [ i ] [ j ] = dpr [ i + 1 ] [ j + 1 ] + 1 ; else dpr [ i ] [ j ] = Math . max ( dpr [ i + 1 ] [ j ] , dpr [ i ] [ j + 1 ] ) ; } } let ans = 0 ; for ( let i = 0 ; i <= N ; i ++ ) { for ( let j = 0 ; j < MAX ; j ++ ) { for ( let x = 0 ; x < pos [ j ] . length ; x ++ ) { if ( dpl [ i ] [ pos [ j ] [ x ] - 1 ] + dpr [ i + 1 ] [ pos [ j ] [ x ] + 1 ] == LCS ) { ans ++ ; break ; } } } } return ans ; } let A = " " , B = " " ; let N = A . length , M = B . length ; document . write ( numberofways ( A , B , N , M ) ) ;