"Isomorphie" von Strings bestimmen
-
Hi
Ich möchte bestimmen, ob zwei Strings isomorph sind. Mit isomorph meine ich hier die Fähigkeit, den einen in den anderen zu überführen, nur indem ich ein Zeichen durch ein anderes, das sonst nicht vorkommt, austausche. Nach dieser Definition sind isomorph:
"a" und "a"
"abc" und "def"
"aaa" und "iii"
"aab" und "xxy"
"ab" und "ba"
"ababa" und "cxcxc"
Nicht isomorph sind:
"aab" und "aaa" (b wurde durch a ersetzt, obwohl a schon vorkommt)
"aab" und "baa"Der naive Ansatz braucht keinen zusätzlichen Speicher aber läuft in O(n^2): Einfach durchiterieren und für jedes Zeichen scannen, ob es später nochmals vorkommt.
Ein anderer Ansatz wäre, die bereits verglichenen Zeichen in einer Tabelle abzulegen; das wäre dann je O(n) in Time und Space. (man denke sich das Alphabet als unendlich gross, sonst würde eine konstante Tabelle von 256 Einträgen ausreichen)Hat jemand eine bessere Idee?
-
Edit: Hmm, nicht ganz.
-
Das müsste sich mit der gleichen Komplexität lösen lassen, die ein Sortieren der Symbole im String erfordert.
Wenn String 1 sortiert wird und gleichzeitig String 2 analog umgeordnet wird, so dass korrespondierende Symbole dort in der gleichen Reihenfolge stehen, ist der Abgleich der Strings im Anschluss offensichtlich mit linearem Aufwand möglich.
-
Dieser Thread wurde von Moderator/in Arcoth aus dem Forum C++ (alle ISO-Standards) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
man könnte noch (zusätzlich) mit Mustererkennung (aa aaa aba abc usw.) arbeiten und/oder mit Wahrscheinlichkeiten.
Beide Strings in eine dritte Syntax umcodieren (eventuell mit Automaten und/oder NN) die dem Vergleich entgegenkommt.
(bzw. gleich ein künstliches neuronales Netz drauf ansetzen).Inwieweit man wo Zeit spart, das hängt auch vom Material ab, von Bibliotheksfunktionen o.ä. d.h. viel herumprobieren (könnte auch noch was bringen).
