Hallo,
wie kann man denn die Stelle finden, ab denen zwei Strings unterschiedlich sind?
Ich habe zwei Strings, diese unterscheiden sich nur an einer Stelle. Diese Stelle ist beliebig viele Zeichen lang.
Wie kann ich nun mit wenig Aufwand den Startindex und die Länge dieser Stelle herausfinden?
Für Ideen wäre ich dankbar.
mfg
punkdevil
circa so:
string hallo1 = "ifsdjik";
string hallo2 = "ifsdjdik";
int hereIsADifference = 0;
for (int i = 0; i < hallo1.Length; i++)
{
if (i > hallo2.Length)
hereIsADifference = i;
if (hallo1[i] != hallo2[i])
hereIsADifference = i;
}
eher so:
string hallo1 = "ifsdjik";
string hallo2 = "ifsdjdik";
int hereIsADifference = -1;
for (int i = 0; i < hallo1.Length; i++)
{
if (i > hallo2.Length)
hereIsADifference = i;
if (hallo1[i] != hallo2[i])
hereIsADifference = i;
}
dann kannst du nämlich unterscheiden, ob die Zeichenketten sich an der Stelle Null oder eben gar nicht unterscheiden
Hallo nin und onlinegurke,
wie kriege ich dann noch die Länge der Stelle raus, an der sich die Strings unterscheiden?
Wenn ich mal ganz frei NiNs Loesung editiere: Ich wuerd's leicht abgewandelt machen.
string string1 = "ifsdjik";
string string2 = "ifsdjdik";
Console.WriteLine(GetDifferencePos(string1, string2));
int GetDifferencePos(string left, string right) {
int hereIsADifference = -1;
if (left.Length < right.Length) {
hereIsADifference = left.Length;
} else if (right.Length < left.Length) {
hereIsADifference = right.Length;
} else {
for (int i = 0; i < left.Length; i++) {
if (left[i] != right[i]) {
hereIsADifference = i;
break;
}
}
}
return hereIsADifference;
}
Pound for pound, plutonium is about as toxic as caffeine when eaten.
Grob..
string string1 = "ifsdjik";
string string2 = "ifsdjdik";
int firstDiff = GetDifferencePos(string1, string2);
int diffLength = 0;
if (firstDiff > -1) {
if (firstDiff >= string1.Length) {
diffLength = string2.Length - firstDiff;
} else if (firstDiff >= string2.Length) {
diffLength = string1.Length - firstDiff;
} else {
for (int i = firstDiff+1; i < string1.Length; i++) {
if (string1[i] == string1[i]) {
diffLength++;
}
}
}
}
Komplett ungetestet. Kann off-by-ones enthalten.. Kaffee?
Pound for pound, plutonium is about as toxic as caffeine when eaten.
@DarKlajid
aus
wie kann man denn die Stelle finden, ab denen zwei Strings unterschiedlich sind? würd ich mal rauslesen, dass die erste Position, ab der die Zeichenketten unterschiedlich sind, gesucht ist. Insofern führt dein Algorithmus u.U. nicht zum Ziel (z.B. "ab" und "bbb" würde bei dir 2 rauskommen, korrekt wäre aber 0)
Voellig korrekt. Ich moechte das bitte gern mit dem "Kein Kaffee" Joker beantworten, lasse aber um anderen den Spass und die Haeme zu goennen oben mal so stehen.. 😉
Danke fuer die Korrektur.
Pound for pound, plutonium is about as toxic as caffeine when eaten.
Die Vorgehensweise die ich bevorzugen würde, wäre, auf die gleiche Art und Weise den letzten Abweichungsindex zu suchen:
int GetFirstDiff(String Input1,String Input2)
{
for (int i = 0; i < Input1.Length; i++)
{
if (i = Input2.Length)
{
return i;
}
if (hallo1[i] != hallo2[i])
{
return i;
}
}
if (Input1.Length<Input2.Length) return Input1.Length
return -1
}
int GetDifferenceLength(String Input1,String Input2)
{
int Start=GetFirstDiff(Input1,Input2)
if (Start=-1) return 0
char chars1[]=Input1.ToCharArray
char chars2[]=Input2.ToCharArray
Array.Reverse(chars1)
Array.Reverse(chars2)
int End=GetFirstDiff(new String(chars1),new String(chars2))
return Math.Max(Input1.Length,Input2.Length)-Start-End
}
Nicht hauen, keine Revanche, aber..
aaaccbbbcc
aaaddbbbdd
Wuerde das nicht bei dir eine Aenderung von 4 - Ende bringen?
Pound for pound, plutonium is about as toxic as caffeine when eaten.
Tja das zeigt ziemlich deutlich, dass das Problem zu schwammig beschrieben ist. Mal ganz davon abgesehen, dass das vom Schwierigkeitsgrad her auch eine Hausaufgabe sein könnte.
e.f.q.
Aus Falschem folgt Beliebiges
Erst sollte mal festgelegt werden, in wie weit unterschiede aufkommen können. wenn definitiv nur an einer stelle unterschiede auftreten, würde ich einmal von vorne jedes zeichen vergleichen.
wird ein unterschiedliches zeichen gefunden, vergleichst du noch einmal jedes zeichen, und zwar beginnst du dann aber am ende des strings.
Bsp:
string 1: "abcdefghijklmno"
string 2: "abcdefgxxxxmno"
nun ist zu klären, ob die länge des unterschieds 5 (nämlich "hijkl") oder 4 ("xxxx") ist.
also sollte einer der beiden als primärer string gelten.
erst wenn das geklärt ist, würde ich mir gedanken über die realisierung und den code machen.
@KochMich: Genauso ist mein Code realisiert 🙂, bei der 'Länge des Unterschiedes' hab ich mich halt für die im Zweifel im größere Variante entschieden.
Und fuer beide Beispiele (onlinegurke & KochMich) sehe ich da das gleiche "Problem":
Wie oben:
aaaccbbbcc <- String1
aaaddbbbdd <- String2
^^ <- (Erster) Unterschied mit Laenge 2
^^^^^^^ <- Das Ergebnis eurer Berechnung zum Unterschied
Wenn die Enden gleich sind:
aaaccbbbccxx <- String1
aaaddbbbddxx <- String2
^^ <- (Erster) Unterschied mit Laenge 2
^^^^^^^ <- Das Ergebnis eurer Berechnung zum Unterschied
Ich versteh nicht warum ihr beide bei der Betrachtung des Strings von hinten noch Gleichheit (hier fuer mich definiert als gleich an Pos. X) ueberprueft, eventuelle gleiche Teile in der Mitte aber ignoriert.
Mein Vorschlag also: Ab dem ersten ungleichen Zeichen werden beide Strings charweise vorwaerts ueberprueft bis a) die Zeichen gleich sind oder b) einer der Strings das Ende erreicht hat.
Pound for pound, plutonium is about as toxic as caffeine when eaten.
Die Diskussion ist schon lange sinnlos, weil nicht klar definiert ist, was gesucht ist.
Fängt ja schon damit an: Was ist ein Unterschied?
e.f.q.
Aus Falschem folgt Beliebiges
@DarKlajid: Es war so definiert, dass es nur eine Unterscheidung gibt, d.h, alle Gleichheiten in der Mitte werden ignoriert.
Hallo,
vielen Dank an alle Poster.
Ich hab im Moment keine Zeit. Ich meld mich morgen oder übermorgen nochmal. Wichtig für die Problemstellung ist auch, dass das ganze performant ist. Die Strings können sehr lang werden (>10000 Zeichen).
Hallo,
ich möchte nocheinmal klar definieren, wie der Stringvergleich aussehen soll.
Ich habe zwei gleiche Strings.
z.B. String1 = qwertzuiop
String 2 = qwertzuiop
In einen der beiden Strings wird ein String eingefügt.
String1 = qwertz123uiop
String2 = qwertzuiop
Nun möchte ich die Stelle finden, an der der Unterschied beginnt und die Länge dieser Stelle ermitteln.
Das Ergebnis wäre also: im String 1: Stelle 6, 3 Zeichen lang
Ich möchte also wissen, wie ich String1 bearbeiten müsste um String2 herauszubekommen.
Das ganze sollte recht performant sein, da die Strings recht lang werden können (>10000 Zeichen).
Wer hat irgendwelche Ideen?
mfg
punkdevil
Hallo punkdevil,
verwende die Algorithmen, die auch beim Unix-Utility diff verwendet werden:
The basic algorithm is described in the papers An O(ND) Difference Algorithm and its Variations by Eugene W. Myers and in A File Comparison Program by Webb Miller and Myers. The algorithm was independently discovered and described in Algorithms for Approximate String Matching, by E. Ukkonen.
herbivore
Hallo herbivore,
gibt es irgendwo eine Beschreibung der Algorithmen oder den Quellcode?
Hallo punkdevil,
bei google?
herbivore