En ciencias de la computación, el problema común de subcadenas más largo es encontrar la cadena más larga que es una subcadena de dos o más cadenas.
Análisis
Dadas dos cadenas ayb, sea dp[i][j] ser la longitud de la subcadena común que termina en un[i] y B[j].
La tabla dp tiene el siguiente aspecto dado a = «abc» yb = «abcd».
Solución Java
public static int getLongestCommonSubstring(String a, String b){ int m = a.length(); int n = b.length(); int max = 0; int[][] dp = new int[m][n]; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(a.charAt(i) == b.charAt(j)){ if(i==0 || j==0){ dp[i][j]=1; }else{ dp[i][j] = dp[i-1][j-1]+1; } if(max < dp[i][j]) max = dp[i][j]; } } } return max; } |
Este es un problema similar al de la subsecuencia común más larga. La diferencia de la solución es que para este problema cuando un[i]! = b[j], dp[i][j] son todos ceros por defecto. Sin embargo, en el problema de subsecuencia común más largo, dp[i][j] los valores se llevan de los valores anteriores, es decir, dp[i-1][j] y dp[i][j-1].
