zwei Strings vergleichen

1337iceskater

Aktives Mitglied
Hallo Leute,

ich habe folgendes Problem: Ich suche einen Algorithmus, der mir möglichst effizient zwei Strings vergleicht. Dabei geht es mir konkret um folgendes (ich erklärs mal an nem Beispiel):

String1: "Hallo Welt"
String2: "Hallo Welten wie geht es euch"

Bsp2:

String1: "Hallo Welt"
String2: "o Welten wie geht es euch denn heute"

String 2 beinhaltet also immer einen gewissen Teil von String1, evtl sogar den ganzen String. Ich möchte jetzt meinen Algorithmus so gestalten, dass ich weiß, ab welcher Stelle in String 2 ich diesen an String 1 anhängen muss, damit nichts verloren geht. Ich möchte also aus Beispiel 2 heraus folgendes Ergebnis aus dem Algorithmus haben:

"en wie geht es euch denn heute"

Ich hoffe, ihr habt mich soweit verstanden und könnt mir evtl helfen (vielleicht gibt es ja auch schon ne Java-Funktion, die ich nur noch nicht kenne).

Vielen Dank schonmal!

LG Stefan
 
Zuletzt bearbeitet von einem Moderator:

Marco13

Top Contributor
Brute Force!?
Code:
for (jedes mögliche Endstück E von A)
{
    if (B.startsWith(E)) return B.substring(E.length());
}
?!
 

1337iceskater

Aktives Mitglied
@Marco13: Ich glaube Brute Force wäre da ein wenig zu Ressourcenhungrig, da die Strings auch gut und gerne mal mehrere Seiten haben können und es wirklich schnell gehen muss.

@henpara: Hier würde ich dann ein "ABAB" erwarten.

Danke auf jeden Fall schonmal für die rege Beteiligung.
 

henpara

Bekanntes Mitglied
nimm 1. char von String 2, wo taucht der bei string 1 als erstes auf. von da an testen ob folgechars gleich sind, bis sie ungleich sind. ist dann ende von string 1 erreicht, bist du fertig, ansonsten selbstaufruf mit substring von string 1 ein char hinter erstes auftauchen von gleichem char.
 

Java123???

Mitglied
Naja, wenn string1 immer der Anfang von string2 ist, dann musst du nur die Länge von string1 herausfinden (z.B. ist string1 = "hallo", dann wäre string1.length() = 5). Wenn du diese Länge hast, dann entfernst du die ersten Zeichen von string2, die ersten 5 (z.B. ist string2 = "hallo welt", dann kannst du mit string2.substring(5) die ersten 5 Zeichen entfernen und hast in string2 nur noch " welt" drin stehen).

Edit: muss natürlich
Java:
string1.substring(string2.length());
heißen, habs oben auch schon geändert.
 
Zuletzt bearbeitet:

1337iceskater

Aktives Mitglied
@henpara: Den Algorithmus hatte ich auch schon auf dem Schirm, aber selbst der ist irgendwann zu lahm :p
@Java: Das Problem ist ja, dass das Ende von String1 zwar immer in String 2 ist aber nicht zwingend der GANZE String 1 ^^
 

henpara

Bekanntes Mitglied
da die Strings auch gut und gerne mal mehrere Seiten haben können und es wirklich schnell gehen muss.
Naja wenn du wirklich alle verschiedenen möglichkeiten überprüfen musst, kommst an einem recourcenfressenden algorithmus nicht vorbei. Sind denn die anteile von string 1, die in string 2 vorkommen total zufällig? oder kommen bestimmte längen quasi garnicht vor? Wenn du die verteilung der längen kennen würdest (zumindest ungefähr) könntest du ja einen "intelligenten" algorithmus schreiben.

Alternativ fällt mir noch ein das ganze quasi von hinten aufzuzäumen:

nehme ganz string1, schau ob er in string 2 am anfang steht, wenn nicht, rufe die methode mit string 1 ohne 1. char auf.
sind dann also maximal string1.length stringvergleiche.
 

1337iceskater

Aktives Mitglied
OK danke Henpara. Ich glaube ich werde die beiden Methoden einfach mal austesten. Vielleicht passen die ja wirklich vom Aufwand her ;)

Danke auf jeden Fall nochmal.
Ich schließe das Thema jetzt einfach mal =)
 

1337iceskater

Aktives Mitglied
Aaaaalsoooo:

Ich habe mich jetzt für folgende Version entschieden:
Java:
for(int i = 0; i < string1.length(); i++){
if(!string1.substring(string1.length()-1-i).equals(string2.substring(0,i){
return string2.substring(i);
}
}
Diese habe ich auch implementiert (zumindest vorläufig). Lief auch, allerdings zu langsam. Daraufhin habe ich nach einer anderen Methode gesucht an diese Strings zu kommen. Jetzt lese ich einfach direkt nur das neue ein und muss somit nicht mehr vergleichen (ich hatte die Methode nur nicht gefunden).
Der Algorithmus oben war aber der effektivste, da er den geringsten Aufwand produzieren würde.

Danke nochmal an alle Beteiligten!
 

Marco13

Top Contributor
Kommt mir irgendwie bekannt vor ;)
Man könnte sich da bestimmt auch was geschickteres überlegen... fragt sich wie der Tradeoff ist, zwischen "Zeit, die man in eine geschickte Lösung steckt" und "Zeit, die man durch die geschicktere Lösung spart"...
 
D

Dow Jones

Gast
In der Bioinformatik sind einige nette Algorithmen für das String matching bekannt. Google mal, da wirst du bestimmt etwas finden das du verwenden kannst (z.B. die Grundidee des Knuth-Morris-Pratt Algos). Bei großen Datenmengen lohnt sich das auf jeden Fall, auch wenn es sich nicht mehr in 3 Zeilen implementieren lässt. :)
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
H RegularExpression zwischen zwei Strings Allgemeine Java-Themen 2
A Ungleicheit von zwei gleichen Strings Allgemeine Java-Themen 3
O Text aus einer Textdatei rausholen, der zwischen zwei Schlüsselworten steht Allgemeine Java-Themen 4
D Zwei Listen vergleichen Allgemeine Java-Themen 7
Tobero Wie berechnet man ob zwei Linien sich schneiden? Allgemeine Java-Themen 2
kodela Zwei gleichzeitig gedrückte Steuertasten Allgemeine Java-Themen 10
X Bedingung zwei mal überprüfen Allgemeine Java-Themen 4
Zrebna Random Number - Generische Formel zwischen zwei INKLUSIVEN Werten Allgemeine Java-Themen 16
D Input/Output Zwischen zwei ID-Räumen unterscheiden und Objekt löschen Allgemeine Java-Themen 16
D OOP Gemeinsamen ID-Raum für zwei Klassen implementieren Allgemeine Java-Themen 7
S Wenn eine Klasse zwei Interfaces mit derselben Methodensignatur implementiert: welche wird aufgerufen? Allgemeine Java-Themen 15
S Kann man Variablen oder Felder definieren deren Typ zwei Interfaces ist..? Allgemeine Java-Themen 9
K Aus String zwei Jahreszahlen auslesen Allgemeine Java-Themen 18
M Wie kann man eine void Methode mit Variablen von zwei verschiedenen Objekten ausführen? Allgemeine Java-Themen 15
VfL_Freak Double mit zwei festen NK-Stellen ausgeben Allgemeine Java-Themen 9
Neoline Methoden Zwei Arrays abwechselnd zusammenführen Allgemeine Java-Themen 15
J Zwei Wavdateien gleichzeitig mit SourceDataLine abspielen Allgemeine Java-Themen 0
D Best Practice Die niedrigste Differenz zwischen zwei Listen ermitteln. Allgemeine Java-Themen 10
J Fahrroute zwischen zwei Punkten finden Allgemeine Java-Themen 1
J Kollision von zwei Kreisen Allgemeine Java-Themen 15
J Transfer von Integer zwischen zwei Clients - RMI Allgemeine Java-Themen 4
S Variablen split-Funkton mit zwei Variabeln verwenden? Allgemeine Java-Themen 4
T Alle Kombinationen aus zwei Arrays Allgemeine Java-Themen 8
G Liste zwischen zwei Kalenderdaten erstellen Allgemeine Java-Themen 3
AssELAss Zwei Arrays / ArrayLists inhaltlich vergleichen Allgemeine Java-Themen 2
P Zwei Applikationen mit einem Job Allgemeine Java-Themen 0
A Lineare Interpolation mit zwei Arrays Allgemeine Java-Themen 4
E Berechnung des Schnittpunktes von zwei Geraden Allgemeine Java-Themen 1
S Zwei String vergleichen, Fehler markieren Allgemeine Java-Themen 3
G Matrix reduzieren zwei Methoden Allgemeine Java-Themen 2
Dechasa Vergleichen von zwei Arrays Allgemeine Java-Themen 4
P Zwei ArrayLists: Ohne die eine überhaupt anzurühren, wird sie verändert Allgemeine Java-Themen 2
S Anwendung zum ausrechnen der Differenz von zwei Tagen Allgemeine Java-Themen 9
F Zwei LinkedHashMaps iterieren und vergleichen Allgemeine Java-Themen 2
M Zwei unterschiedliche JAR Dateien mit ANT erstellen Allgemeine Java-Themen 8
B Fehler beim Auslesen von Einstellungen. Zwei ähnliche Blöcke, nur eins geht. Allgemeine Java-Themen 5
L Zwei Files miteinander vergleichen und Grafisch darstellen Allgemeine Java-Themen 1
T Zwei Wortendungen vergleichen ohne .equals Allgemeine Java-Themen 10
F Webstart zwei Java Versionen / aktivieren bzw deaktivieren Allgemeine Java-Themen 2
S Zwei Comparable (compareTo) vergleichen Allgemeine Java-Themen 6
E zwei Gleitkommazahlen durcheinander dividieren Allgemeine Java-Themen 2
X Generic muss zwei Klassen/Interfaces erfüllen Allgemeine Java-Themen 5
turmaline OOP zwei gleiche Methoden mit kleinen Unterschieden Allgemeine Java-Themen 15
C Threads Zwei Threads greifen auf LinkedList zu. Allgemeine Java-Themen 12
T Wie heißt ein Binärbaum, dessen Knoten immer zwei Kinder haben müssen? Allgemeine Java-Themen 2
C ActionListener zwei Buttons zuweisen Allgemeine Java-Themen 11
M Eclipse drei slashs durch zwei ersetzen? Allgemeine Java-Themen 3
C Buchstaben, die in zwei Wörtern vorkommen Allgemeine Java-Themen 13
J Gleiche Packagestruktur in zwei *.jar Dateien Allgemeine Java-Themen 4
G Zwei bytes vergleichen Allgemeine Java-Themen 2
B zwei-dimensionale Collections bzw. Array mit Indizes Allgemeine Java-Themen 3
C Zwei Arrays vereinen Allgemeine Java-Themen 3
K Objekt-Austausch zwischen zwei Programmen über System-Clipboard Allgemeine Java-Themen 5
H Zwei verschiedene Dateien mittels einem Binärstream übertragen? Allgemeine Java-Themen 13
N hashCode() für zwei ints Allgemeine Java-Themen 5
turmaline Gleichheit von zwei Maps Map <String, Map <String, String>> Allgemeine Java-Themen 30
N Wie Listenabgleich auf zwei CPU Cores auslagern? Allgemeine Java-Themen 6
D Zufall wahr bzw. falsch mit zwei Faktoren Allgemeine Java-Themen 10
H Datenaustausch zwischen zwei Java-Programmen Allgemeine Java-Themen 5
H Ausgabe von zwei Textfeldern Allgemeine Java-Themen 3
H Zwei unabhängige Threads miteinander kommunizieren lassen Allgemeine Java-Themen 3
G zwei mal synchronized Allgemeine Java-Themen 5
Z zwei Daten vergleichen Allgemeine Java-Themen 4
C ArrayList anhand von zwei Attributen sortieren Allgemeine Java-Themen 4
S Alle Elemente von zwei Listen vergleichen Allgemeine Java-Themen 10
T IText: Zwei A4 PDF´s auf ein A3 PDF´s Allgemeine Java-Themen 2
J Verschachtelte ListIteratoren um in zwei Listen hin und herzugehen Allgemeine Java-Themen 5
A Differenz zwischen zwei Uhrzeiten Allgemeine Java-Themen 7
H Shortcut ruft zwei Menu-punkte auf Allgemeine Java-Themen 5
J Zwei konstruktoren? Allgemeine Java-Themen 8
A zwei listen vergleichen und unterschiede anzeigen Allgemeine Java-Themen 3
J Zwei sortierte Listen zusammenfassen Allgemeine Java-Themen 8
G Linked List zwischen zwei Threds übergeben Allgemeine Java-Themen 11
J zwei HashMaps vereinen Allgemeine Java-Themen 3
C Viele Informationen aus zwei Collections vergleichen Allgemeine Java-Themen 2
G Jfreechart zwei charts Allgemeine Java-Themen 2
S Zwei Anwendungen unter Tomcat Allgemeine Java-Themen 4
T Anzahl Tage zwischen zwei Daten - Stunde fehlt? Allgemeine Java-Themen 2
V Zwei ArrayList(s) vergleichen Allgemeine Java-Themen 6
T Überprüfen ob zwei Farben ähnlich sind Allgemeine Java-Themen 14
M zwei main-Methoden Allgemeine Java-Themen 7
P zwei JFrames zusammenhängen Allgemeine Java-Themen 4
A Summe und Produkt von zwei Feldern ( arrays) Allgemeine Java-Themen 9
M HashMap kapselt zwei Objekte aber wie baut man eine Matrix? Allgemeine Java-Themen 2
H zwei Date Variablen überschreiben sich Allgemeine Java-Themen 2
2 Tage zwischen zwei Datumsdaten zählen Allgemeine Java-Themen 2
G Tage zwischen zwei Datumsdaten zählen Allgemeine Java-Themen 3
J Zwei String auf ähnlichkeiten untersuchen? Allgemeine Java-Themen 3
C kürzester weg zwischen zwei Punkten, Koordinaten finden Allgemeine Java-Themen 15
B zwei Bilder miteinander vergleichen Allgemeine Java-Themen 25
L Anzahl Tage zwischen zwei Kalenderdaten Allgemeine Java-Themen 5
P Threadprogrammierung - zwei Threads parallel - einer beendet Allgemeine Java-Themen 3
G Kommunikation von zwei Java-Programmen Allgemeine Java-Themen 3
A Zusammenfassen von zwei Dateien (wie beim DOS-Befehl copy) Allgemeine Java-Themen 6
S zwei Arrays zusammenfassen Allgemeine Java-Themen 14
L Zwei Hashtables statt einer? Allgemeine Java-Themen 6
M zwei Threads - ein singleton-Objekt Allgemeine Java-Themen 3
A funktion schiffeZeichnen zwei mal aufrufen Allgemeine Java-Themen 16
G zwei Rückgabewerte gefordert. Was tun ? Allgemeine Java-Themen 10
Chucky Zwei Binärbäume vereinigen Allgemeine Java-Themen 7

Ähnliche Java Themen

Neue Themen


Oben