El problema de la subsecuencia común más larga (LCS) es el problema de encontrar la subsecuencia más larga común a todas las secuencias en un conjunto de secuencias (a menudo solo dos secuencias).
Análisis
Deja dp[i+1][j+1] ser la longitud de la subsecuencia común más larga de las cadenas a & b, cuando un[i] y B[j] se comparan entre sí. (0 <= i <= a.length-1, 0 <= j <= b.length-1)
Solución Java
public static int getLongestCommonSubsequence(String a, String b){ int m = a.length(); int n = b.length(); int[][] dp = new int[m+1][n+1]; for(int i=0; i<=m; i++){ for(int j=0; j<=n; j++){ if(i==0 || j==0){ dp[i][j]=0; }else if(a.charAt(i-1)==b.charAt(j-1)){ dp[i][j] = 1 + dp[i-1][j-1]; }else{ dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]); } } } return dp[m][n]; } |
