Mit 2 Strings wie:
%Vor%Ich möchte nur den Teil löschen, der in beiden Strings üblich ist und dann den Rest verketten. Ich muss sagen, dass ich nur den linksbündigen Teil löschen muss, damit ich
bekommeZuerst dachte ich, ein Muster zu verwenden und dann secrhh dafür, dies ist jedoch nicht möglich, da ich das Muster nicht im Voraus kenne (die Länge der übereinstimmenden Zeichen ist variabel)
Dann dachte ich nach der ganzen Zeichenfolge b in a , dann, wenn kein Erfolg, lösche ein Zeichen in der Zeichenfolge a (Letzte, seit ich die meisten linken nicht übereinstimmenden Zeichenfolge beibehalten möchte) und dann Schleife, bis ich habe keine weiteren Zeichen in b
wie
Also wäre die Antwort nur a + toAppend ;
Gibt es eine Möglichkeit, dies effizienter zu machen? (vielleicht in LINQ?)
Wie @lavin richtig anzeigt c kann irgendwo in a vorkommen, während es ein Präfix von b ist. Zum Beispiel, wenn a=AAT und b=AAG , Code sollte AATG zurückgeben.
Der Grund dafür ist, dass die gemeinsame Zeichenfolge, die links beginnt, c=AA ist. Wir löschen dies aus b und dann erhalten wir a=AAT mit der resultierenden G
resultierend
%Vor%Ein anderes Beispiel wäre:
%Vor%hier
%Vor%Das Ergebnis sollte
sein %Vor%(alle Arrays und Strings sind in dieser Antwort 0)
Zuerst möchte ich darauf hinweisen, dass das Problem von OP verwirrend ist. Nehmen wir an, c ist der gemeinsame Teil von a und b . Das Beispiel von Input und Output von OP legt nahe, dass c das Suffix von a und gleichzeitig das Präfix von b sein muss. Ich sehe einige der obigen Antworten angenommen dieses Verständnis des Problems.
Die ursprüngliche Implementierung von OP legt jedoch nahe, dass c irgendwo in a vorkommen kann, während sie ein Präfix von b ist, weil Sie a.Contains(auxString) verwenden. Das heißt, für a=AAT und b=AAG gibt Ihr Code AATG zurück. Die Antworten anderer Personen geben jedoch AATAAG zurück.
Es gibt also zwei mögliche Interpretationen Ihres Problems. Bitte klären.
Zweitens wird angenommen, dass die Größe der ersten Zeichenfolge a N und die zweite Zeichenfolge b M ist, im Gegensatz zur Lösung O(N*M) in der ursprünglichen Lösung und vorhandenen Antworten ein O(N+M) Algorithmus kann mit einem der folgenden Verfahren erreicht werden: KMP, Suffix Array, Suffix Tree, Z-Algorithmus.
Ich werde hier kurz beschreiben, wie man den Z-Algorithmus verwendet, um dieses Problem zu lösen, da es im Stackoverflow viel weniger erwähnt wird als bei anderen.
Informationen zum Z-Algorithmus finden Sie Ссылка
Im Grunde wird für eine Zeichenkette S der Länge L ein Array Z der Länge L berechnet, wobei Z[i] gleich dem längsten gemeinsamen Präfix von S und S[i:] (%) ist. co_de% bedeutet Teilzeichenfolge von S[i:] ausgehend von der Position S ).
Für dieses Problem kombinieren wir die Strings i und a mit b ( d=b+a vor b ) und berechnen das Array a der kombinierten Zeichenkette Z . Mit diesem d -Array können wir leicht das längste Präfix von Z ermitteln, das auch in b vorkommt.
Für eine mögliche Interpretation eines der Probleme, bei dem a das Suffix von c und das Präfix von a sein muss:
und die Antwort wäre:
%Vor% Für mögliche Interpretation zwei des Problems, in dem b das Präfix von c sein muss, und kann irgendwo in b sein:
nochmal die Antwort wäre:
%Vor%Der Unterschied in diesen beiden Fällen ist diese Zeile:
%Vor% Um diese Zeile zu verstehen, denken Sie daran, dass a das längste gemeinsame Präfix der Zeichenfolgen Z[i] und d ist, dann:
d[i:]
d=b+a von i bis M , das ist der Bereich von M+N-1 in a . So ist d gleich d[i:] . Und die Länge von a[i-M:] ist a[i-M:] . N-(i-M)=N+M-i mit d beginnt, überprüft, ob b gleich Z[i] ist, prüft, ob N+M-i auch ein Präfix von a[i-M:] ist. Wenn sie tatsächlich gleich sind, dann haben wir eine gemeinsame Zeichenkette b gefunden, die das Präfix von c ist, und auch ein Suffix von b . a gefunden haben, die ein Präfix von c ist und in b ab der Position a vorkommt und nicht garantiert das Ende von% erreicht. co_de%. Dies funktioniert, um den ersten Punkt zu finden, dass b den Schwanz von a überlappt:
In diesem Beispiel wird 9 zurückgegeben.
Die endgültige Ausgabe ist:
%Vor%Was ergibt:
%Vor% Dies alles setzt voraus, dass die Überlappung am Ende von a und am Anfang von b auftritt.
Linq wird dir hier nicht wirklich helfen.
Wenn n und m die Länge der linken und rechten Nachrichten sind, sieht es so aus, als hätten Sie ein O ( nm) Lösung ...
Fist komprimiere deine Nachrichten.
Da es nur 4 mögliche Buchstaben gibt, können Sie sie auf 2 Bits codieren.
Das ist, 4 Buchstaben für Bytes. (statt 2 byte byte).
In einem 32-Bit-Vergleich werden Sie 16 statt 2 Buchstaben prüfen.
Dann (mystisches, spät betrunkenes Denken) führe zwei parallele und inkrementelle FFT durch, indem du die Daten von den Enden, die du verschmelzen willst (vom Ende für die linke Nachricht und vom Anfang für die rechte), wenn die FFT übereinstimmt Wahrscheinlichkeit haben eine Übereinstimmung. Überprüfen Sie es.
Die tatsächliche Umsetzung wird wahrscheinlicher sein:
Lesen Sie die Daten von den Enden, die Sie zusammenführen möchten (vom Ende für die linke Nachricht und dem Start für die rechte Nachricht) und während Sie die "Buchstaben" der zwei Nachrichten lesen:
Erstellen Sie die Summe der Daten. L[n-1]+L[n-2]+L[n-3]+L[n-4]+.. und R[0]+R[1]+R[2]+R[3]+..
Erstellen Sie die alternative Summe. L[n-1]-L[n-2]+L[n-3]-L[n-4]+.. und R[0]-R[1]+R[2]-R[3]+..
Erstellen Sie die 2-alternative Summe. L[n-1]+L[n-2]-L[n-3]-L[n-4]+.. und R[0]+R[1]-R[2]-R[3]+..
und einige mehr (4,8,16-alternative Summen).
Wenn Sie eine Übereinstimmung haben. Überprüfen Sie es.
Wenn echte DNA viele falsch positive Übereinstimmungen ergibt, schreiben Sie ein Papier darüber.
[EDIT]
Die Summe wird übereinstimmen. OK. Aber die alternative Summe wird nur im absoluten Wert übereinstimmen.
Wenn die Nachrichten ... 4 5 6 und 5 6 7 ...
Die Summe der beiden ersten Werte ist in beiden Fällen 5 + 6 = 11.
Aber die alternative Summe wird -5 + 6 = 1 und 5 - 6 = -1 sein.
Für die 2,4 ..-alternative Summe haben Sie ein Problem ...
Sie benötigen andere Operationen, bei denen die Reihenfolge keine Rolle spielt. Wie Multiplikation und XOR.
Hier ist meins. Ich denke, es ist das prägnanteste und ich sehe keinen Weg, es effizienter zu machen.
%Vor%Tags und Links algorithm c# string-matching