Laden...

Unterschied zwischen zwei Strings

Erstellt von punkdevil vor 17 Jahren Letzter Beitrag vor 16 Jahren 6.153 Views
P
punkdevil Themenstarter:in
992 Beiträge seit 2007
vor 17 Jahren
Unterschied zwischen zwei Strings

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

738 Beiträge seit 2007
vor 17 Jahren

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;
            }

O
778 Beiträge seit 2007
vor 17 Jahren

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

P
punkdevil Themenstarter:in
992 Beiträge seit 2007
vor 17 Jahren

Hallo nin und onlinegurke,

wie kriege ich dann noch die Länge der Stelle raus, an der sich die Strings unterscheiden?

D
386 Beiträge seit 2007
vor 17 Jahren

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.

D
386 Beiträge seit 2007
vor 17 Jahren

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.

O
778 Beiträge seit 2007
vor 17 Jahren

@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)

D
386 Beiträge seit 2007
vor 17 Jahren

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.

O
778 Beiträge seit 2007
vor 17 Jahren

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
}

D
386 Beiträge seit 2007
vor 17 Jahren

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.

T
512 Beiträge seit 2006
vor 17 Jahren

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

K
60 Beiträge seit 2007
vor 17 Jahren

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.

O
778 Beiträge seit 2007
vor 17 Jahren

@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.

K
60 Beiträge seit 2007
vor 17 Jahren

ach jau, stimmt. 😁 na dann is ja alles klaro! 👍

D
386 Beiträge seit 2007
vor 17 Jahren

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.

T
512 Beiträge seit 2006
vor 17 Jahren

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

O
778 Beiträge seit 2007
vor 17 Jahren

@DarKlajid: Es war so definiert, dass es nur eine Unterscheidung gibt, d.h, alle Gleichheiten in der Mitte werden ignoriert.

P
punkdevil Themenstarter:in
992 Beiträge seit 2007
vor 17 Jahren

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).

P
punkdevil Themenstarter:in
992 Beiträge seit 2007
vor 16 Jahren

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

49.485 Beiträge seit 2005
vor 16 Jahren

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

P
punkdevil Themenstarter:in
992 Beiträge seit 2007
vor 16 Jahren

Hallo herbivore,

gibt es irgendwo eine Beschreibung der Algorithmen oder den Quellcode?

49.485 Beiträge seit 2005
vor 16 Jahren

Hallo punkdevil,

bei google?

herbivore