Dieser Artikel beschreibt die Methode von Java, um die größte gemeinsame Substring von zwei Zeichenfolgen zu finden. Teilen Sie es für Ihre Referenz wie folgt weiter:
Vor kurzem habe ich eine Voraussetzung für einen Textvergleich in meiner Projektarbeit. Nachdem ich diesen Zeitraum untersucht habe, habe ich den Inhalt dieses Blogs zusammengefasst: Finden Sie die größte gemeinsame Substring von zwei Saiten.
Algorithmusidee: Berechnen Sie die gemeinsame Substring von zwei Zeichenfolgen basierend auf Graphen. Für spezifische Algorithmus -Ideen finden Sie in der folgenden Abbildung:
Eingabezeichenfolge S1: Achmacmh Eingangszeichenfolge S2: Macham
Der spezifische Implementierungscode lautet wie folgt:
Paket cn.lulei.comPare; Import Java.util.ArrayList; Import Java.util.Collections; Java.util.comParator importieren; importieren java.util.list; öffentliche Klasse StringCompare {private int a; Privat int B; public String getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // S1 Länge macht Zeile B = S2.Length (); // Setzen Sie die Spalte der S2 -Länge, wenn (a == 0 || b == 0) {return ""; } // Setzen Sie die passende Matrix boolean [] [] array = new boolean [a] [b]; für (int i = 0; i <a; i ++) {char c1 = s1.charat (i); für (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == C2) {Array [i] [j] = true; } else {Array [i] [j] = false; }}}} // Suchen Sie alle gemeinsamen Faktor -Zeichenfolgen und speichern Sie die Informationen als Startposition und Länge in Bezug auf die zweite Zeichenfolgeliste <ChildString> ChildStrings = New ArrayList <kindString> (); für (int i = 0; i <a; i ++) {getMaxSort (i, 0, Array, ChildStrings); } für (int i = 1; i <b; i ++) {getMaxSort (0, i, Array, ChildStrings); } // sortieren (childstrings); if (childstrings.size () <1) {return ""; } // Geben Sie den maximalen gemeinsamen Faktor String int max = childstrings.get (0) .MaxLength zurück; StringBuffer sb = new StringBuffer (); für (ChildString S: ChildStrings) {if (max! = smaxLength) {break; } SB.Append (S2.Substring (s.maxStart, s.maxStart + smaxLength)); sb.Append ("/n"); } return sb.toString (); } // Sortierung, Rückblende private void sortieren (Liste <ChildString> Liste) {Collections.sort (Liste, neuer Komparator <ChildString> () {public int Compare (ChildString O1, ChildString O2) {return o2.MaxLength - O1.MaxLength;}}); } // Die gemeinsame Faktor -Zeichenfolge auf einem Slash private void GetMaxSort (int i, int j, boolean [] [] Array, Liste <ChildString> Sortbean) {int länge = 0; int start = j; für (; i <a && j <b; i ++, j ++) {if (Array [i] [j]) {Länge ++; } else {sortbean.add (New ChildString (Länge, Start)); Länge = 0; start = j + 1; } if (i == a-1 || j == b-1) {sortBean.add (neue Kinderstring (Länge, Start)); }}} // öffentliche Faktorklasse 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 auto-generierter Methode stub system.out.println (new StringCompare (). }} Das endgültige Ausführungsergebnis des Programms ist:
Zum Vergleich der beiden Dateien denke ich persönlich, dass diese algorithmische Idee (und jetzt und zur Implementierung), die in einem zukünftigen Blog geschrieben wird, verwiesen werden kann.
Im obigen Implementierungsprozess werden alle gemeinsamen Substring -Informationen mit einem Array gespeichert und dann wird das größte Substring sortiert. Wenn diese Methode nur das größte Substring finden soll, ist der Algorithmus nicht sehr vernünftig. Daher werden folgende Änderungen vorgenommen. List spart nur das größte Substring in der aktuellen Berechnung. Die spezifische Implementierung ist wie folgt:
/ ***@Beschreibung: String -Vergleich*/ package com.lulei.test; Import Java.util.ArrayList; importieren java.util.list; öffentliche Klasse StringCompare {private int a; Privat int B; private int maxLength = -1; public String getMaxLengthCommonstring (String S1, String S2) {if (s1 == null || s2 == null) {return null; } a = s1.length (); // S1 Länge wird verwendet, um Zeile B = S2.Length (); // S2 Länge zu erstellen, um die Spalte zu erstellen, wenn (a == 0 || b == 0) {return ""; } // Setzen Sie die passende Matrix boolean [] [] array = new boolean [a] [b]; für (int i = 0; i <a; i ++) {char c1 = s1.charat (i); für (int j = 0; j <b; j ++) {char c2 = s2.charat (j); if (c1 == C2) {Array [i] [j] = true; } else {Array [i] [j] = false; }}} // Alle gemeinsamen Faktor -Zeichenfolgen beenden und die Informationen als Startposition und Länge relativ zur zweiten String -Liste speichern. für (int i = 0; i <a; i ++) {getMaxSort (i, 0, Array, ChildStrings); } für (int i = 1; i <b; i ++) {getMaxSort (0, i, Array, ChildStrings); } StringBuffer sb = new StringBuffer (); für (ChildString S: ChildStrings) {sb.Append (S2.Substring (s.maxstart, s.maxstart + smaxLength)); sb.Append ("/n"); } return sb.toString (); } // Die gemeinsame Faktor -Zeichenfolge auf einem Slash private void GetMaxSort (int i, int j, boolean [] [] Array, Liste <ChildString> Sortbean) {int länge = 0; int start = j; für (; i <a && j <b; i ++, j ++) {if (Array [i] [j]) {Länge ++; } else {// Fügen Sie alle Substrings direkt hinzu, das folgende Urteil speichert nur das derzeit größte Substring //sortbean.add(new Childtring (Länge, Start)); if (length == maxLength) {sortbean.add (neue Kinderstring (Länge, Start)); } else if (Länge> maxLength) {sortbean.clear (); MaxLength = Länge; sortbean.add (neue Kinderstring (Länge, Start)); } Länge = 0; start = j + 1; } if (i == a-1 || j == b-1) {// direkt hinzufügen, alle Substrings speichern, das folgende Urteil spart nur das aktuelle größte Substring //sortbean.add(new Childtring (Länge, Start)); if (length == maxLength) {sortbean.add (neue Kinderstring (Länge, Start)); } else if (Länge> maxLength) {sortbean.clear (); MaxLength = Länge; sortbean.add (neue Kinderstring (Länge, Start)); }}}}} // 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 automatisch generierte Methode stub system.out.println (new StringCompare (). }} Danke fürs Lesen, ich hoffe, es kann Ihnen helfen. Vielen Dank für Ihre Unterstützung für diese Seite!