Berechnen Sie die Läufe eines Strings

11

Betrachten Sie die folgenden Definitionen aus Die Anzahl der Läufe in einer Zeichenfolge von W. Rytter. Beachten Sie, dass Wort, Zeichenfolge und Teilzeichenfolge ungefähr Synonyme sind.

Ein Lauf in einer Zeichenfolge ist ein nicht erweiterbares (mit derselben minimalen Periode) periodisches Segment in einer Zeichenfolge.

Eine Periode p eines Wortes w ist eine positive ganze Zahl p, so dass w [i] = w [i + p] ist, wenn beide Seiten dieser Gleichung definiert sind. Per (w) bezeichne die Größe der kleinsten Periode von w. Wir sagen, dass ein Wort w periodisch ist, wenn per (w) <= | w | / 2.

Betrachten Sie zum Beispiel die Zeichenfolge x = abcab. per(abcab) = 3wie x[1] = x[1+3] = a, x[2]=x[2+3] = bund es gibt keine kleinere Periode. Die Zeichenfolge abcabist daher nicht periodisch. Die Zeichenfolge ababist jedoch periodisch gemäß (abab) = 2.

Ein Lauf (oder eine maximale Periodizität) in einem String w ist ein Intervall [i ... j] mit j> = i, so dass

  • w [i ... j] ist ein periodisches Wort mit der Periode p = per (w [i ... j])
  • Es ist maximal. Formal ist weder w [i-1] = w [i-1 + p] noch w [j + 1] = w [j + 1-p]. Informell kann der Lauf nicht in einem größeren Lauf mit derselben Periode enthalten sein.

Bezeichne mit RUNS (w) die Menge der Läufe von w.

Beispiele

Die vier Läufe von atattattsind [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tattatt.

Die Zeichenfolge aabaabaaaacaacacenthält die folgenden 7 Läufe:

[1,2] = aa, [4,5] = aa, [7,10] = aaaa, [12,13] = aa, [13,16] = acac, [1,8] = aabaabaa, [9 , 15] = Aacaaca.

Ihre Ausgabe sollte eine Liste von Läufen sein. Jeder Lauf sollte das Intervall angeben, das er darstellt, muss jedoch den Teilstring selbst nicht ausgeben. Die genaue Formatierung kann beliebig sein.

In den Beispielen wird die 1-Indizierung verwendet. Sie können jedoch stattdessen die 0-Indizierung verwenden, wenn dies bequemer ist.

AUFGABE

Schreiben Sie Code, der eine Zeichenfolge w angibt, und geben Sie RUNS (w) aus.

Sprachen und Eingabe

Sie können eine beliebige Sprache verwenden und die Eingabezeichenfolge in der am besten geeigneten Form verwenden. Sie müssen jedoch ein vollständiges Programm angeben und ein Beispiel für Ihren Code anzeigen, der auf der Beispieleingabe ausgeführt wird.

code-golf string
quelle
4
Schöne Herausforderung, aber gibt es einen guten Grund, die Standardfunktionen außer Kraft zu setzen und nicht zuzulassen?
Martin Ender
@ MartinEnder Es ist nur meine Präferenz. Dies erleichtert es den Menschen, einfach Code zu kopieren, einzufügen und selbst auszuprobieren, was wiederum die Antworten für mehr Menschen interessanter macht.
4
Das verursacht aber auch viel Overhead-Code, was die Konkurrenz für Sprachen mit einer ausführlichen Syntax unfair macht. Ich würde zum Beispiel nicht in Java Golf spielen, wenn ich class A{public static ...}jedes Mal schreiben müsste, wenn ich Golfcode spielen wollte
Bassdrop Cumberwubwubwub
@BassdropCumberwubwubwub Ich kann sehen, dass es Vor- und Nachteile gibt. Ich wiege die Profis stärker. Ich denke, es ist auf jeden Fall am interessantesten, die Länge der Golf-Antworten in ähnlichen Sprachen zu vergleichen, anstatt beispielsweise APL mit Python zu vergleichen.
"Ein Lauf ist maximal, wenn er nicht vollständig in einem größeren Lauf enthalten ist", aber in Ihrem ersten Beispiel ist [7,8] vollständig in [2,8] enthalten. Oder sprechen Sie ausschließlich von Läufen, die denselben Teilstring wiederholen?
Aditsu beendet, weil SE

Antworten:

2

Pyth, 38 Bytes

{smm,hk+ekdfgaFTdcx1xM.ttB+0qVQ>QdZ2Sl

  m                                 SlQ   map for d in [1, …, len(input)]:
                            qVQ>Qd          pairwise equality of input[:-d] and input[d:]
                        tB+0                duplicate this list, prepending 0 to one copy
                      .t          Z         transpose, padding with 0
                    xM                      pairwise xor
                  x1                        find all occurrences of 1
                 c                 2        chop into groups of 2
           f                                filter for groups T such that:
             aFT                              the absolute difference between its elements
            g   d                             is greater than or equal to d
   m                                        map for groups k:
     hk                                       first element
    ,  +ekd                                   pair with the last element plus d
 s                                        concatenate
}                                         deduplicate

Testsuite

Anders Kaseorg
quelle
Ich bekomme "[[3, 5], [6, 8], [0, 4], [1, 8]]" von "atattatt". Stellt [3,5] "tt" dar? Es wäre großartig, wenn Sie den von Ihnen verwendeten Algorithmus auch auf hoher Ebene erklären könnten.
@Lembik Ja, [i, j]stellt die Ausgangsscheibe zwischen (0-indizierte) Zeichen i-1und iund endend zwischen Zeichen j-1und j. Dies ist die Standardkonvention in Pyth und den meisten vernünftigen Sprachen, wie es sein sollte (siehe hier und hier ).
Anders Kaseorg
Groß. Ist es möglich, Ihre Lösung intuitiv zu beschreiben? Ich kann es leider nicht von Ihrer Codebeschreibung zurückentwickeln.
1
@Lembik Angenommen, wir suchen nach Läufen der Periode d. Wir finden alle Stellen, an denen Zeichen i mit Zeichen i + d übereinstimmt. Wir finden dann Läufe von mindestens d aufeinanderfolgenden solchen Orten. Wiederholen Sie dies für alle d. Wir müssen am Ende deduplizieren, weil die reale Periode möglicherweise nur ein Teiler von d war.
Anders Kaseorg
1

CJam, 66

q:A,2m*{~A>_@)_@<2*@@2*<=},{_2$-2>2,.+={+}&}*]{[_1=\)\0=2*)+]}%_&p

Probieren Sie es online aus

Kurze Erklärung:

Der Algorithmus arbeitet in 4 Schritten (die ersten 3 entsprechen den 3 Hauptblöcken, die Sie beobachten können):

  1. Suchen Sie alle [ Längenindex ] -Paare, die einem duplizierten Teilstring entsprechen (z. B. ein aba aba aaacaacac). Dies sind Teile von Läufen.
  2. Verketten Sie Paare, die Teil desselben Laufs sind, dh aufeinanderfolgende Indizes und dieselbe Länge / Periode.
  3. Konstruieren Sie die tatsächlichen Läufe, indem Sie den minimalen Index und den maximalen Index + 2 * Länge - 1 verwenden.
  4. Entfernen Sie am Ende die doppelten Läufe (die das gleiche Intervall haben, das mit einem anderen Zeitraum erhalten wurde).

Ich würde gerne mehr Golf spielen, daher kann sich dies ändern.

Aditsu beenden, weil SE böse ist
quelle
Danke dafür. Könnten Sie bitte den Algorithmus erklären, den Sie auch verwendet haben?
1
@Lembik ok, aktualisiert
Aditsu beendet, weil SE