Java implementa la coincidencia de cadenas para encontrar la subcadena común máxima de dos cuerdas

Este artículo describe el método de Java para encontrar la subcadena común más grande de dos cuerdas. Compártelo para su referencia, como sigue:

Recientemente, tengo un requisito para la comparación de texto en el trabajo de mi proyecto. Después de estudiar este período de tiempo, he resumido el contenido de este blog: encuentre la subcadena común más grande de dos cuerdas.

Idea de algoritmo: Calcule la subcadena común de dos cadenas basadas en gráficos. Para ideas de algoritmos específicas, consulte la siguiente figura:

Cadena de entrada S1: AChMACMH Cadena de entrada S2: Macham

1. El paso A es dividir las cadenas S1 y S2 bytes respectivamente para formar una matriz bidimensional;
2. Los valores en la matriz bidimensional se muestran en b. Por ejemplo, los valores en la primera fila y la primera columna representan si los primeros bytes de las cadenas S2 y S1 son iguales. Si son iguales, es 1, de lo contrario es 0, y finalmente se genera la matriz bidimensional que se muestra en B;
3. Encuentre el factor común en la línea diagonal en una matriz bidimensional (la línea diagonal es el valor de la esquina inferior derecha del elemento A, es decir, el siguiente elemento de un [i] [j] es un [i+1] [j+1]; el factor común es una cadena compuesta de la posición donde 1 es);
4. Ordene todos los factores comunes, devolviendo el valor del factor común más grande.

El código de implementación específico es el siguiente:

 paquete cn.lulei.compare; import java.util.arrayList; import java.util.collections; importar java.util.comparator; import java.util.list; clase pública StringCompare {private int a; privado int b; public String getMaxLengthComstring (String S1, String S2) {if (S1 == NULL || S2 == NULL) {return null; } a = S1.length (); // La longitud S1 hace que la línea b = s2.length (); // establezca la columna de longitud s2 if (a == 0 || b == 0) {return ""; } // Establecer la matriz de coincidencia booleana [] [] array = new Boolean [a] [b]; para (int i = 0; i <a; i ++) {char c1 = s1.charat (i); para (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}}} // Encuentre todas las cadenas de factores comunes, guarde la información como la posición inicial y la longitud en relación con la segunda lista de cadenas <ChildString> ChildStrings = New ArrayList <ChildString> (); para (int i = 0; i <a; i ++) {getMaxSort (i, 0, matriz, childstrings); } para (int i = 1; i <b; i ++) {getMaxSort (0, i, matriz, childstrings); } // sortear (childStrings); if (childStrings.size () <1) {return ""; } // devuelve la cadena máxima del factor común int max = childStrings.get (0) .maxLength; StringBuffer sb = new StringBuffer (); para (ChildString s: ChildStrings) {if (max! = s.maxlength) {break; } sb.append (s2.substring (s.maxstart, s.maxstart + s.maxLength)); sb.append ("/n"); } return sb.ToString (); } // clasificación, flashback private void sort (list <ChildString> list) {collections.sort (list, nuevo comparador <ChildString> () {public int Compare (ChildString O1, ChildString O2) {return o2.maxlength - o1.maxlength;}}); } // Encuentre la cadena del factor común en un vacío privado de corte getMaxsort (int i, int j, boolean [] [] matriz, list <ChildString> sortBean) {int longitud = 0; int inicio = j; for (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {longitud ++; } else {sortBean.add (nuevo childString (longitud, inicio)); longitud = 0; inicio = j + 1; } if (i == a-1 || j == b-1) {sortBean.add (nuevo childString (longitud, inicio)); }}} // Clase de factor público ChildString {int maxLength; int maxStart; ChildString (int maxLength, int maxStart) {this.maxLength = maxLength; this.maxstart = maxStart; }} / ** * @param args * / public static void main (string [] args) {// tODO método auto-generado stub.out.println (new StringComPare (). }}

El resultado de ejecución final del programa es:

Para comparar los dos archivos, personalmente creo que esta idea algorítmica puede referirse (y ahora y para la implementación), que se escribirá en un blog futuro.

En el proceso de implementación anterior, toda la información de subcadena común se guarda con una matriz, y luego se ordene la subcadena más grande. Si este método es solo para encontrar la subcadena más grande, el algoritmo no es muy razonable. Por lo tanto, se realizan las siguientes modificaciones. La lista solo guarda la subcadena más grande en el cálculo actual. La implementación específica es la siguiente:

 / ***@Descripción: comparación de cadenas*/ paquete com.lulei.test; import java.util.arrayList; import java.util.list; clase pública StringCompare {private int a; privado int b; private int maxLength = -1; public String getMaxLengthComstring (String S1, String S2) {if (S1 == NULL || S2 == NULL) {return null; } a = S1.length (); // La longitud S1 se usa para hacer la fila b = s2.length (); // La longitud S2 se usa para hacer columna si (a == 0 || b == 0) {return ""; } // Establecer la matriz de coincidencia booleana [] [] array = new Boolean [a] [b]; para (int i = 0; i <a; i ++) {char c1 = s1.charat (i); para (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}} // termina todas las cadenas de factores comunes y guarde la información como la posición de inicio y la longitud en relación con la segunda lista de cadenas <ChildString> ChildStrings = New ArrayList <ChildString> (); para (int i = 0; i <a; i ++) {getMaxSort (i, 0, matriz, childstrings); } para (int i = 1; i <b; i ++) {getMaxSort (0, i, matriz, childstrings); } StringBuffer sb = new StringBuffer (); para (ChildString S: ChildStrings) {sb.append (s2.substring (s.maxstart, s.maxstart + s.maxLength)); sb.append ("/n"); } return sb.ToString (); } // Encuentre la cadena del factor común en un vacío privado de corte getMaxsort (int i, int j, boolean [] [] matriz, list <ChildString> sortBean) {int longitud = 0; int inicio = j; for (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {longitud ++; } else {// Agregar directamente, guarde todas las subcadenas, el juicio siguiente solo guardará la subcadena más grande actual //sortbean.add(new ChildString (longitud, inicio)); if (longitud == maxLength) {sortBean.Add (new ChildString (longitud, inicio)); } else if (longitud> maxlength) {sortBean.clear (); maxlength = longitud; sortBean.add (nuevo ChildString (longitud, inicio)); } longitud = 0; inicio = j + 1; } if (i == a-1 || j == b-1) {// Agregar directamente, guarde todas las subcadenas, el juicio siguiente solo guarda la subcadena más grande actual //sortbean.add(new ChildString (longitud, inicio)); if (longitud == maxLength) {sortBean.Add (new ChildString (longitud, inicio)); } else if (longitud> maxlength) {sortBean.clear (); maxlength = longitud; sortBean.add (nuevo ChildString (longitud, inicio)); }}}}} // clase de factor público childString {int maxLength; int maxStart; ChildString (int maxLength, int maxStart) {this.maxLength = maxLength; this.maxstart = maxStart; }} / ** * @param args * / public static void main (string [] args) {// tODO método generado automático stub.out.println (new StringCompare (). GetMaxLengthCommonstring ("ABCDEF", "Defabc")); }}

Gracias por leer, espero que pueda ayudarte. ¡Gracias por su apoyo para este sitio!