Java implémente la correspondance des cordes pour trouver la sous-chaîne commune maximale de deux chaînes

Cet article décrit la méthode de Java pour trouver la plus grande sous-chaîne commune de deux chaînes. Partagez-le pour votre référence, comme suit:

Récemment, j'ai une exigence de comparaison de texte dans mon travail de projet. Après avoir étudié cette période de temps, j'ai résumé le contenu de ce blog: trouver la plus grande sous-chaîne commune de deux chaînes.

Idée d'algorithme: calculer la sous-chaîne commune de deux chaînes en fonction des graphiques. Pour des idées d'algorithmes spécifiques, veuillez vous référer au chiffre suivant:

Chaîne d'entrée S1: ACHMACMH String d'entrée S2: Macham

1. L'étape A consiste à diviser respectivement les cordes S1 et S2 pour former un tableau bidimensionnel;
2. Les valeurs du tableau bidimensionnel sont indiquées en b. Par exemple, les valeurs de la première ligne et de la première colonne représentent si les premiers octets des chaînes S2 et S1 sont égaux. S'ils sont égaux, il est 1, sinon il est 0, et enfin le tableau bidimensionnel indiqué en B est généré;
3. Trouvez le facteur commun sur la ligne diagonale dans un tableau bidimensionnel (la ligne diagonale est la valeur du coin inférieur droit de l'élément A, c'est-à-dire que l'élément suivant d'un [i] [j] est a [i + 1] [j + 1]; le facteur commun est une chaîne composée de la position où 1 est);
4. Triez tous les facteurs communs, renvoyant la valeur du plus grand facteur commun.

Le code d'implémentation spécifique est le suivant:

 Package CN.lulei. import java.util.arraylist; Importer java.util.collections; Importer java.util.comparator; Importer java.util.list; classe publique StringCompare {private int a; Int privé B; String public getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // la longueur S1 fait la ligne b = s2.length (); // définir la colonne de la longueur s2 if (a == 0 || b == 0) {return ""; } // Définit la matrice correspondante boolean [] [] array = new Boolean [a] [b]; pour (int i = 0; i <a; i ++) {char c1 = s1.charat (i); pour (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}}} // Trouvez toutes les chaînes de facteur communes, enregistrez les informations en tant que position de départ et longueur par rapport à la deuxième liste de chaînes <fildString> childStrings = new ArrayList <fildString> (); pour (int i = 0; i <a; i ++) {getMaxSort (i, 0, array, childStrings); } pour (int i = 1; i <b; i ++) {getMaxSort (0, i, array, childStrings); } // Tri tri (ChildStrings); if (childStrings.size () <1) {return ""; } // Renvoie la chaîne de facteur commune maximale int max = childStrings.get (0) .maxLength; StringBuffer sb = new StringBuffer (); pour (childstring s: childStrings) {if (max! = s.maxLength) {break; } SB.APPEND (S2.SubString (S.MaxStart, S.MaxStart + S.maxLength)); sb.append ("/ n"); } return sb.toString (); } // tri, flashback private void tri (list <filstring> list) {collections.sort (list, nouveau comparateur <fildString> () {public int compare (childstring o1, childstring o2) {return o2.maxlength - o1.maxlength;}}); } // Trouvez la chaîne de facteur commune sur un slash private void getMaxsort (int i, int j, booléan [] [] array, list <filstring> sortbean) {int length = 0; int start = j; for (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {longueur ++; } else {sortbean.add (new childstring (longueur, start)); longueur = 0; start = j + 1; } if (i == a-1 || j == b-1) {sortbean.add (new childstring (longueur, start)); }}} // Classe de facteur public 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 menetated method Stub System.out.println (new StringCompare (). getMaxLengthCommonstring ("ACHMACMH", "Macham")); }}

Le résultat d'exécution final du programme est:

À titre de comparaison des deux fichiers, je pense personnellement que cette idée algorithmique peut être référée (et maintenant et pour la mise en œuvre), qui sera écrite dans un futur blog.

Dans le processus de mise en œuvre ci-dessus, toutes les informations de sous-chaîne courantes sont enregistrées avec un tableau, puis la plus grande sous-chaîne est triée. Si cette méthode est juste pour trouver la plus grande sous-chaîne, l'algorithme n'est pas très raisonnable. Par conséquent, les modifications suivantes sont apportées. La liste économise uniquement la plus grande sous-chaîne dans le calcul actuel. La mise en œuvre spécifique est la suivante:

 / ** * @ Description: Comparaison des chaînes * / package com.lulei.test; import java.util.arraylist; Importer java.util.list; classe publique StringCompare {private int a; Int privé B; private int maxLength = -1; String public getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // La longueur S1 est utilisée pour faire de la ligne b = s2.length (); // la longueur S2 est utilisée pour faire de la colonne if (a == 0 || b == 0) {return ""; } // Définit la matrice correspondante boolean [] [] array = new Boolean [a] [b]; pour (int i = 0; i <a; i ++) {char c1 = s1.charat (i); pour (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == c2) {array [i] [j] = true; } else {array [i] [j] = false; }}} // Terminez toutes les chaînes de facteurs communs et enregistrez les informations en tant que position de départ et longueur par rapport à la deuxième liste de chaînes <fildString> childStrings = new ArrayList <fildString> (); pour (int i = 0; i <a; i ++) {getMaxSort (i, 0, array, childStrings); } pour (int i = 1; i <b; i ++) {getMaxSort (0, i, array, childStrings); } StringBuffer sb = new StringBuffer (); pour (ChildString S: ChildStrings) {SB.APPEND (S2.SubString (S.MaxStart, S.MaxStart + S.MaxLength)); sb.append ("/ n"); } return sb.toString (); } // Trouvez la chaîne de facteur commune sur un slash private void getMaxsort (int i, int j, booléan [] [] array, list <filstring> sortbean) {int length = 0; int start = j; for (; i <a && j <b; i ++, j ++) {if (array [i] [j]) {longueur ++; } else {// Ajouter directement, enregistrer toutes les sous-chaînes, le jugement suivant n'aura que la plus grande sous-chaîne actuelle //sortbean.add(New ChildString (longueur, start)); if (longueur == maxLength) {sortbean.add (new childstring (longueur, start)); } else if (longueur> maxLength) {sortbean.clear (); maxLength = longueur; SORTBEAN.ADD (New ChildString (longueur, démarrage)); } longueur = 0; start = j + 1; } if (i == a-1 || j == b-1) {// Ajouter directement, enregistrer toutes les sous-chaînes, le jugement suivant n'enregistre que la plus grande sous-chaîne actuelle //sortbean.add(New Childstring (longueur, start)); if (longueur == maxLength) {sortbean.add (new childstring (longueur, start)); } else if (longueur> maxLength) {sortbean.clear (); maxLength = longueur; SORTBEAN.ADD (New ChildString (longueur, démarrage)); }}}}} // public Factor Class 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 meneterated method Stub System.out.println (new StringCompare (). getMaxLengthCommonstring ("ABCDEF", "Defabc")); }}

Merci d'avoir lu, j'espère que cela peut vous aider. Merci pour votre soutien à ce site!