Considérez les définitions suivantes tirées du nombre d'exécutions dans une chaîne de W. Rytter. Notez que mot, chaîne et sous-chaîne sont tous à peu près synonymes.

Une exécution dans une chaîne est un segment périodique non extensible (avec la même période minimale) dans une chaîne.

Une période p d'un mot w est tout entier positif p tel que w [i] = w [i + p] chaque fois que les deux côtés de cette équation sont définis. Soit per (w) la taille de la plus petite période de w. On dit qu'un mot w est périodique ssi (w) <= | w | / 2.

Par exemple, considérez la chaîne x = abcab. per(abcab) = 3comme x[1] = x[1+3] = a, x[2]=x[2+3] = bet il n'y a pas de période plus courte. La chaîne abcabn'est donc pas périodique. Cependant, la chaîne ababest périodique selon (abab) = 2.

Une course (ou périodicité maximale) dans une chaîne w est un intervalle [i ... j] avec j> = i, tel que

• w [i ... j] est un mot périodique avec la période p = per (w [i ... j])
• C'est maximal. Formellement, ni w [i-1] = w [i-1 + p] ni w [j + 1] = w [j + 1-p]. De manière informelle, l'exécution ne peut pas être contenue dans une exécution plus grande avec la même période.

Notons RUNS (w) l'ensemble des séries de w.

Exemples

Les quatre séries de atattattsont [4,5] = tt, [7,8] = tt, [1,4] = atat, [2,8] = tattatt.

La chaîne aabaabaaaacaacaccontient les 7 exécutions suivantes:

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

Votre sortie doit être une liste d'exécutions. Chaque exécution doit spécifier l'intervalle qu'elle représente mais n'a pas besoin de sortir la sous-chaîne elle-même. La mise en forme exacte peut être celle qui vous convient.

Les exemples utilisent l'indexation 1, mais vous êtes libre d'utiliser à la place l'indexation 0 si cela est plus pratique.

TÂCHE

Écrivez le code qui, étant donné une chaîne w, sortez RUNS (w).

Langues et saisie

Vous pouvez utiliser n'importe quelle langue que vous aimez et prendre la chaîne d'entrée sous la forme qui vous convient le mieux. Vous devez cependant donner un programme complet et vous devez montrer un exemple de votre code s'exécutant sur l'exemple d'entrée.

Pyth, 38 octets

{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

Suite de tests

CJam, 66

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

Essayez-le en ligne

Brève explication:

L'algorithme fonctionne en 4 étapes (les 3 premières d'entre elles correspondant aux 3 blocs principaux que vous pouvez observer):

1. Trouver toutes les paires [index de longueur] qui correspondent à une sous-chaîne dupliquée (comme un aba aba aaacaacac); ce sont des parties de pistes.
2. Concaténer des paires qui font partie de la même série, c'est-à-dire des indices consécutifs et la même longueur / période.
3. Construisez les parcours réels, en prenant l'index minimum et l'index maximum + 2 * longueur - 1.
4. À la fin, supprimez les exécutions dupliquées (qui sont le même intervalle obtenu avec une période différente)

Je voudrais jouer davantage au golf, donc tout est susceptible de changer.