Bei dieser Herausforderung geht es darum, Code zu schreiben, um das folgende Problem zu lösen.
Bei zwei Zeichenfolgen A und B sollte Ihr Code den Start- und den Endindex einer Teilzeichenfolge von A mit den folgenden Eigenschaften ausgeben.
- Die Teilzeichenfolge von A sollte auch mit einer Teilzeichenfolge von B übereinstimmen.
- Es sollte keine Teilzeichenfolge von A mehr geben, die die erste Eigenschaft erfüllt.
Zum Beispiel:
A = xxxappleyyyyyyy
B = zapplezzz
Die Teilzeichenfolge apple
mit Indizes 4 8
(Indexierung von 1) wäre eine gültige Ausgabe.
Funktionalität
Sie können davon ausgehen, dass die Eingabe standardmäßig in oder in einer Datei im lokalen Verzeichnis erfolgt. Dies ist Ihre Wahl. Das Dateiformat besteht einfach aus zwei Zeichenfolgen, die durch eine neue Zeile getrennt sind. Die Antwort sollte ein vollständiges Programm sein und nicht nur eine Funktion.
Schließlich möchte ich Ihren Code an zwei Teilzeichenfolgen testen, die den Zeichenfolgen in http://hgdownload.cse.ucsc.edu/goldenPath/hg38/chromosomes/ entnommen sind .
Ergebnis
Dies ist Code-Golf mit einem Twist. Ihr Code muss rechtzeitig ausgeführt O(n)
werden. Dabei n
handelt es sich um die Gesamtlänge der Eingabe.
Sprachen und Bibliotheken
Sie können jede Sprache verwenden, die einen frei verfügbaren Compiler / Interpreter / etc hat. für Linux. Sie sollten nur Standard-Open-Source-Bibliotheken verwenden, die nicht für diese Aufgabe entwickelt wurden. Im Streitfall zähle ich dies als jede Bibliothek, die entweder standardmäßig in Ihrer Sprache enthalten ist oder die Sie von einem Standard-Repository aus auf einem Ubuntu-Standardcomputer installieren können.
Nützliche Informationen
Es gibt mindestens zwei Möglichkeiten, um dieses Problem in linearer Zeit zu lösen. Eine besteht darin, zuerst den Suffix-Baum und die zweite zunächst das Suffix-Array und das LCP-Array zu berechnen.
- Hier finden Sie eine vollständige und (möglicherweise zu) ausführliche Erklärung der linearen Zeitsuffix-Baumkonstruktion (es stellt sich heraus, dass einige der Zahlen leider durcheinander sind). Unter https://stackoverflow.com/questions/9452701/ukkonens-suffix-tree-algorithm-in-plain-english gibt es auch eine sehr nette SO-Antwort zur linearen Zeitsuffix- Baumkonstruktion . Es enthält auch einen Link zum Quellcode. Eine weitere ausführliche Erklärung finden Sie hier , diesmal mit einer vollständigen Lösung in C.
- Abschnitt 2 von http://www.cs.cmu.edu/~guyb/realworld/papersS04/KaSa03.pdf enthält einen linearen Algorithmus zur Erstellung von Zeitsuffix-Arrays, und Anhang A enthält C ++ - Quellcode. In dieser Antwort erfahren Sie, wie Sie die längste häufig verwendete Teilzeichenfolge https://cs.stackexchange.com/questions/9555/computing-the-longest-common-substring-of-two-strings- using- suffix- arrays berechnen . Abschnitt 5 von https://courses.csail.mit.edu/6.851/spring12/scribe/lec16.pdf, zu dem auch eine Videovorlesung https://courses.csail.mit.edu/6.851/spring12/lectures/L16 gehört .html erklärt auch den gleichen Algorithmus ab 1:16:00.
quelle
O(n) time
Bist du sicher, dass es möglich ist?Antworten:
Python 2, 646 Bytes
Hierbei wird der in "Simple Linear Work Suffix Array Construction" von Kärkkäinen und Sanders beschriebene Schräglaufalgorithmus verwendet. Die in diesem Artikel enthaltene C ++ - Implementierung fühlt sich bereits ein wenig "golfen" an, aber es gibt noch viel Raum, um sie zu verkürzen. Zum Beispiel können wir rekursiv arbeiten, bis wir zu einem Array der Länge eins kommen, anstatt wie in der Arbeit einen Kurzschluss zu verursachen, ohne die
O(n)
Anforderung zu verletzen .Für den LCP-Teil folgte ich "Linear-Time Longest-Common-Prefix-Berechnung in Suffix-Arrays und deren Anwendungen" von Kusai et al.
Das Programm gibt aus,
1 0
ob die längste gemeinsame Teilzeichenfolge leer ist.Hier ist ein Entwicklungscode, der eine frühere Version des Programms enthält, die der C ++ - Implementierung etwas genauer folgt, einige langsamere Vergleichsansätze und einen einfachen Testfallgenerator:
quelle