[Diese Frage ist ein Follow-up, um die Läufe einer Zeichenfolge zu berechnen ]
Eine Periode
p
eines Stringsw
ist eine positive ganze Zahl,p
so dassw[i]=w[i+p]
immer dann , wenn beide Seiten dieser Gleichung definiert sind. Lassen Sieper(w)
bezeichnen die Größe der kleinsten Periode vonw
. Wir sagen, dass ein Stringw
ein periodisches iff istper(w) <= |w|/2
.
Informell ist eine periodische Zeichenfolge also nur eine Zeichenfolge, die aus einer anderen Zeichenfolge besteht, die mindestens einmal wiederholt wird. Die einzige Schwierigkeit besteht darin, dass wir am Ende der Zeichenfolge keine vollständige Kopie der wiederholten Zeichenfolge benötigen, solange diese mindestens einmal vollständig wiederholt wird.
Betrachten Sie beispielsweise die Zeichenfolge x = abcab
. per(abcab) = 3
wie x[1] = x[1+3] = a
, x[2]=x[2+3] = b
und es gibt keine kleinere Periode. Die Zeichenfolge abcab
ist daher nicht periodisch. Die Zeichenfolge ababa
ist jedoch periodisch als per(ababa) = 2
.
Als weitere Beispiele abcabca
, ababababa
und abcabcabc
sind auch periodisch.
Für diejenigen, die reguläre Ausdrücke mögen, erkennt dieser, ob eine Zeichenfolge periodisch ist oder nicht:
\b(\w*)(\w+\1)\2+\b
Die Aufgabe besteht darin, alle maximal periodischen Teilzeichenfolgen in einer längeren Zeichenfolge zu finden. Diese werden in der Literatur manchmal als Läufe bezeichnet .
Ein Teilstring
w
ist ein maximaler periodischer Teilstring (run), wenn er periodisch ist und wederw[i-1] = w[i-1+p]
nochw[j+1] = w[j+1-p]
. Informell kann der "Lauf" nicht in einem größeren "Lauf" mit demselben Zeitraum enthalten sein.
Da zwei Durchläufe dieselbe Zeichenfolge darstellen können, die an verschiedenen Stellen in der Gesamtzeichenfolge vorkommt, werden die Durchläufe in Intervallen dargestellt. Hier wird die obige Definition in Intervallen wiederholt.
Ein Lauf (oder maximaler periodischer Teilstring) in einem String
T
ist ein Intervall[i...j]
mitj>=i
, so dass
T[i...j]
ist ein periodisches Wort mit der Periodep = per(T[i...j])
- Es ist maximal. Formal weder
T[i-1] = T[i-1+p]
nochT[j+1] = T[j+1-p]
. Informell kann der Lauf nicht in einem größeren Lauf mit demselben Zeitraum enthalten sein.
Bezeichnen Sie durch RUNS(T)
die Menge der Läufe in Zeichenfolge T
.
Beispiele für Läufe
Der vier maximal periodische Teil (läuft) in String
T = atattatt
istT[4,5] = tt
,T[7,8] = tt
,T[1,4] = atat
,T[2,8] = tattatt
.Die Zeichenfolge
T = aabaabaaaacaacac
enthält die folgenden 7 maximal periodischen Strings (Läufe):T[1,2] = aa
,T[4,5] = aa
,T[7,10] = aaaa
,T[12,13] = aa
,T[13,16] = acac
,T[1,8] = aabaabaa
,T[9,15] = aacaaca
.Die Zeichenfolge
T = atatbatatb
enthält die folgenden drei Läufe. Sie sind:T[1, 4] = atat
,T[6, 9] = atat
undT[1, 10] = atatbatatb
.
Hier verwende ich die 1-Indizierung.
Die Aufgabe
Schreiben Sie Code so, dass Sie für jede Ganzzahl n, die bei 2 beginnt, die größte Anzahl von Läufen ausgeben, die in einer binären Zeichenfolge der Länge enthalten sind n
.
Ergebnis
Ihre Punktzahl ist die höchste, die n
Sie in 120 Sekunden erreicht haben, sodass k <= n
niemand anders eine richtigere Antwort als Sie gepostet hat. Wenn Sie alle optimalen Antworten haben, erhalten Sie die Punktzahl für den höchsten n
Beitrag, den Sie verfassen. Aber auch wenn Ihre Antwort nicht optimal ist, können Sie die Punktzahl erhalten, wenn niemand anders sie schlagen kann.
Sprachen und Bibliotheken
Sie können jede verfügbare Sprache und Bibliothek verwenden, die Sie mögen. Wo immer möglich, wäre es gut, wenn Sie Ihren Code ausführen könnten. Fügen Sie daher bitte eine vollständige Erklärung dazu bei, wie Sie Ihren Code unter Linux ausführen / kompilieren, wenn dies überhaupt möglich ist.
Beispiel optima
Im Folgenden: n, optimum number of runs, example string
.
2 1 00
3 1 000
4 2 0011
5 2 00011
6 3 001001
7 4 0010011
8 5 00110011
9 5 000110011
10 6 0010011001
11 7 00100110011
12 8 001001100100
13 8 0001001100100
14 10 00100110010011
15 10 000100110010011
16 11 0010011001001100
17 12 00100101101001011
18 13 001001100100110011
19 14 0010011001001100100
20 15 00101001011010010100
21 15 000101001011010010100
22 16 0010010100101101001011
Was genau soll mein Code ausgeben?
Für jeden n
Code sollte eine einzelne Zeichenfolge und die Anzahl der darin enthaltenen Läufe ausgegeben werden.
Mein Computer Die Timings werden auf meinem Computer ausgeführt. Dies ist eine Ubuntu-Standardinstallation auf einem AMD FX-8350 Eight-Core-Prozessor. Dies bedeutet auch, dass ich in der Lage sein muss, Ihren Code auszuführen.
Führende Antworten
- 49 von Anders Kaseorg in C . Einfach eingefädelt und mit L = 12 (2 GB RAM) ausgeführt.
- 27 durch cdlane in C .
quelle
{0,1}
-strings berücksichtigen möchten, geben Sie dies bitte ausdrücklich an. Andernfalls könnte das Alphabet möglicherweise unendlich sein, und ich verstehe nicht, warum Ihre Testfälle optimal sein sollten, da Sie anscheinend auch nur nach{0,1}
Zeichenfolgen gesucht haben.n
bis zu durchsucht12
und es hat das binäre Alphabet nie übertroffen . Aus heuristischer Sicht würde ich erwarten, dass eine Binärzeichenfolge optimal ist, da das Hinzufügen weiterer Zeichen die Mindestlänge eines Durchlaufs erhöht.Antworten:
C
Dies führt eine rekursive Suche nach optimalen Lösungen durch, die mithilfe einer Obergrenze für die Anzahl der Läufe, die mit dem unbekannten Rest der Zeichenfolge abgeschlossen werden könnten, stark eingeschränkt werden. Die Berechnung der oberen Schranke verwendet eine gigantische Nachschlagetabelle, deren Größe durch die Konstante gesteuert wird
L
(L=11
: 0,5 GiB,:L=12
2 GiB,:L=13
8 GiB).Auf meinem Laptop sind es in 100 Sekunden n = 50; Die nächste Zeile kommt bei 142 Sekunden.
Ausgabe:
Hier finden Sie alle optimalen Sequenzen für n ≤ 64 (nicht nur die lexikografisch erste), die mit einer modifizierten Version dieses Programms und vielen Stunden Berechnungszeit generiert wurden.
Eine bemerkenswerte nahezu optimale Sequenz
Die Präfixe der unendlichen fraktalen Sequenz
das ist invariant unter der Transformation 101 ↦ 10100, 00 ↦ 101:
scheinen eine nahezu optimale Anzahl von Läufen zu haben - immer innerhalb von 2 von optimal für n ≤ 64. Die Anzahl der Läufe in den ersten n Zeichen geteilt durch n Ansätze (13 - 5√5) / 2 2 0.90983. Es stellt sich jedoch heraus, dass dies nicht das optimale Verhältnis ist - siehe Kommentare.
quelle
Da es kein Rennen ist, wenn es nur ein Pferd gibt, reiche ich meine Lösung ein, obwohl es nur ein Bruchteil der Geschwindigkeit von Anders Kaseorg und ein Drittel nur so kryptisch ist. Kompilieren mit:
Das Herzstück meines Algorithmus ist ein einfaches Shift- und XOR-Schema:
Ein Durchlauf von Nullen im XOR-Ergebnis, der größer oder gleich der aktuellen Periode / Schicht ist, zeigt einen Durchlauf in der ursprünglichen Zeichenfolge für diese Periode an. Daran können Sie erkennen, wie lange der Lauf dauerte und wo er beginnt und endet. Der Rest des Codes ist Overhead, der die Situation einrichtet und die Ergebnisse dekodiert.
Ich hoffe, es wird nach zwei Minuten auf Lembiks Maschine mindestens 28 sein. (Ich habe eine pthread-Version geschrieben, aber nur geschafft, sie noch langsamer laufen zu lassen.)
Ausgabe:
quelle
-O3
soll nicht "unsicher" sein. Es aktiviert die automatische Vektorisierung, aber hier gibt es wahrscheinlich nichts zu vektorisieren. Es kann manchmal den Code verlangsamen, z. B. wenn ein branchless cmov für etwas verwendet wird, das von einem Branch sehr gut vorhergesagt worden wäre. Aber normalerweise sollte es helfen. In der Regel lohnt es sich, auch Clang zu testen, um herauszufinden, welcher von gcc oder Clang besseren Code für eine bestimmte Schleife liefert. Außerdem hilft es fast immer-march=native
,-mtune=native
eine Binärdatei zu verwenden , oder zumindest, wenn Sie noch eine Binärdatei benötigen, die überall ausgeführt wird.