Comment savoir si une chaîne se répète en Python?

352

Je cherche un moyen de tester si une chaîne donnée se répète ou non pour toute la chaîne.

Exemples:

[
    '0045662100456621004566210045662100456621',             # '00456621'
    '0072992700729927007299270072992700729927',             # '00729927'
    '001443001443001443001443001443001443001443',           # '001443'
    '037037037037037037037037037037037037037037037',        # '037'
    '047619047619047619047619047619047619047619',           # '047619'
    '002457002457002457002457002457002457002457',           # '002457'
    '001221001221001221001221001221001221001221',           # '001221'
    '001230012300123001230012300123001230012300123',        # '00123'
    '0013947001394700139470013947001394700139470013947',    # '0013947'
    '001001001001001001001001001001001001001001001001001',  # '001'
    '001406469760900140646976090014064697609',              # '0014064697609'
]

sont des chaînes qui se répètent, et

[
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

sont des exemples de ceux qui ne le font pas.

Les sections répétitives des chaînes qui me sont données peuvent être assez longues et les chaînes elles-mêmes peuvent contenir 500 caractères ou plus, donc parcourir chaque caractère en essayant de créer un modèle puis en vérifiant le modèle par rapport au reste de la chaîne semble terriblement lent. Multipliez cela par des centaines de chaînes et je ne vois aucune solution intuitive.

J'ai un peu examiné les expressions rationnelles et elles semblent bonnes lorsque vous savez ce que vous recherchez, ou au moins la longueur du motif que vous recherchez. Malheureusement, je ne connais ni l'un ni l'autre.

Comment savoir si une chaîne se répète et si c'est le cas, quelle est la sous-séquence répétée la plus courte?

John
la source
15
parcourir chaque caractère en essayant de construire un motif puis vérifier le motif par rapport au reste de la chaîne semble terriblement lent - mais est-ce?
Tim
2
@AvinashRaj Cela ne correspond qu'à une partie d'une chaîne, pas à la totalité.
John
11
@AvinashRaj L'OP demande toutes les solutions possibles. La question à laquelle vous liez accepte uniquement la solution regex . Notez que regex peut être en mesure de résoudre le problème mais en beaucoup plus de temps que nécessaire. Par exemple, une solution optimale (c'est-à-dire un temps linéaire) utiliserait l'arborescence des suffixes du texte. Il vous suffit de trouver la sous-chaîne répétée la plus longue et de vérifier les longueurs.
Bakuriu
2
@ TigerhawkT3 Le véritable ensemble de données est beaucoup trop volumineux et difficile à manier, mais les exemples de la question en font partie, et si vous le souhaitez, en voici d'autres .
John

Réponses:

570

Voici une solution concise qui évite les expressions régulières et les boucles in-Python lentes:

def principal_period(s):
    i = (s+s).find(s, 1, -1)
    return None if i == -1 else s[:i]

Voir la réponse du Wiki de la communauté lancée par @davidism pour les résultats de référence. En résumé,

La solution de David Zhang est clairement gagnante, surpassant toutes les autres d'au moins 5 fois pour le grand ensemble d'exemples.

(Les mots de cette réponse, pas les miens.)

Ceci est basé sur l'observation qu'une chaîne est périodique si et seulement si elle est égale à une rotation non triviale d'elle-même. Félicitations à @AleksiTorhamo pour avoir réalisé que nous pouvons alors récupérer la période principale de l'index de la première occurrence de sin (s+s)[1:-1], et pour m'avoir informé des options startet endarguments de Python string.find.

David Zhang
la source
19
Vous pouvez l'étendre pour trouver la sous-séquence répétitive la plus courte en utilisant .find()ou à la .index()place de in, par exemple. (s+s).find(s, 1, -1).
Aleksi Torhamo, le
11
De plus, je pense que ce (s+s).find(s, 1, -1)sera (très légèrement) plus rapide que (s+s)[1:-1].find(s), au moins pour les chaînes plus grandes, car le découpage signifie que vous devez créer une autre copie de (presque) la chaîne entière.
Aleksi Torhamo, le
13
C'est comme si vous prenez une onde sin ou cos d'une fonction périodique et la déplacez vers la droite. Puisqu'il est entièrement périodique, les vagues finiront par correspondre parfaitement ... Les parallèles mathématiques avec cette solution sont tout simplement phénoménaux. :) J'aimerais pouvoir vous donner + ∞ votes positifs.
Shashank
6
La récente mise à jour de Guido vers PEP 8 est pertinente ici: "Soyez cohérent dans les instructions de retour. Soit toutes les instructions de retour dans une fonction doivent renvoyer une expression, soit aucune ne doit le faire. Si une instruction de retour renvoie une expression, toute instruction de retour où aucune valeur n'est retourné doit explicitement indiquer ceci comme return None, et une déclaration de retour explicite doit être présente à la fin de la fonction (si accessible). "
Zero Piraeus
8
@WayneConrad Prenez une chaîne, disons, détachez "abcd"le caractère à droite et collez-la à gauche pour obtenir "dabc". Cette procédure est appelée rotation d'une chaîne vers la droite de 1 caractère . Répétez plusieurs nfois pour faire pivoter une chaîne vers la droite de ncaractères. Maintenant, observez que si nous avons une chaîne de kcaractères, la rotation vers la droite de n'importe quel multiple klaisse la chaîne inchangée. Une rotation non triviale d'une chaîne est une rotation dont le numéro de caractère n'est pas un multiple de la longueur de la chaîne.
David Zhang
181

Voici une solution utilisant des expressions régulières.

import re

REPEATER = re.compile(r"(.+?)\1+$")

def repeated(s):
    match = REPEATER.match(s)
    return match.group(1) if match else None

En répétant les exemples de la question:

examples = [
    '0045662100456621004566210045662100456621',
    '0072992700729927007299270072992700729927',
    '001443001443001443001443001443001443001443',
    '037037037037037037037037037037037037037037037',
    '047619047619047619047619047619047619047619',
    '002457002457002457002457002457002457002457',
    '001221001221001221001221001221001221001221',
    '001230012300123001230012300123001230012300123',
    '0013947001394700139470013947001394700139470013947',
    '001001001001001001001001001001001001001001001001001',
    '001406469760900140646976090014064697609',
    '004608294930875576036866359447',
    '00469483568075117370892018779342723',
    '004739336492890995260663507109',
    '001508295625942684766214177978883861236802413273',
    '007518796992481203',
    '0071942446043165467625899280575539568345323741',
    '0434782608695652173913',
    '0344827586206896551724137931',
    '002481389578163771712158808933',
    '002932551319648093841642228739',
    '0035587188612099644128113879',
    '003484320557491289198606271777',
    '00115074798619102416570771',
]

for e in examples:
    sub = repeated(e)
    if sub:
        print("%r: %r" % (e, sub))
    else:
        print("%r does not repeat." % e)

... produit cette sortie:

'0045662100456621004566210045662100456621': '00456621'
'0072992700729927007299270072992700729927': '00729927'
'001443001443001443001443001443001443001443': '001443'
'037037037037037037037037037037037037037037037': '037'
'047619047619047619047619047619047619047619': '047619'
'002457002457002457002457002457002457002457': '002457'
'001221001221001221001221001221001221001221': '001221'
'001230012300123001230012300123001230012300123': '00123'
'0013947001394700139470013947001394700139470013947': '0013947'
'001001001001001001001001001001001001001001001001001': '001'
'001406469760900140646976090014064697609': '0014064697609'
'004608294930875576036866359447' does not repeat.
'00469483568075117370892018779342723' does not repeat.
'004739336492890995260663507109' does not repeat.
'001508295625942684766214177978883861236802413273' does not repeat.
'007518796992481203' does not repeat.
'0071942446043165467625899280575539568345323741' does not repeat.
'0434782608695652173913' does not repeat.
'0344827586206896551724137931' does not repeat.
'002481389578163771712158808933' does not repeat.
'002932551319648093841642228739' does not repeat.
'0035587188612099644128113879' does not repeat.
'003484320557491289198606271777' does not repeat.
'00115074798619102416570771' does not repeat.

L'expression régulière (.+?)\1+$est divisée en trois parties:

  1. (.+?)est un groupe correspondant contenant au moins un (mais aussi peu que possible) de n'importe quel caractère (car il +?n'est pas gourmand ).

  2. \1+ vérifie au moins une répétition du groupe correspondant dans la première partie.

  3. $vérifie la fin de la chaîne pour s'assurer qu'il n'y a pas de contenu supplémentaire non répétitif après les sous-chaînes répétées (et l'utilisation re.match()garantit qu'il n'y a pas de texte non répétitif avant les sous-chaînes répétées).

Dans Python 3.4 et versions ultérieures, vous pouvez supprimer $et utiliser à la re.fullmatch()place, ou (dans n'importe quel Python au moins aussi loin que 2.3), aller dans l'autre sens et utiliser re.search()avec l'expression régulière ^(.+?)\1+$, qui sont tous plus à votre goût qu'autre chose.

Zero Piraeus
la source
6
Je ne sais pas pourquoi ce doublé concis n'est pas la réponse la plus votée. Les autres réponses ne sont pas mauvaises, mais celle-ci est bien meilleure. (Il peut utiliser l' expression régulière fréquemment dénigrée , mais je peux l'inspecter beaucoup plus facilement que les autres réponses beaucoup plus longues, qui sont pleines de blocs imbriqués, de fautes de frappe potentielles, d'erreurs hors-ligne, etc.) Ah bien, le pire est mieux Je suppose.
Paul Draper
9
Je pense qu'il y a deux raisons principales à cela: 1) certains programmeurs aiment plus les mathématiques que les expressions rationnelles, et 2) car la variation de la longueur et de la nature des chaînes d'entrée rend les réponses différentes plus performantes, les chaînes de cas de bord ultra-longues (qui peuvent même ne pas apparaître dans les données réelles) font apparaître cette solution sous-optimale.
TigerhawkT3
parfois vous rencontrez de grands préjugés envers les expressions régulières. Ive avait 2 gestionnaires qui ont interdit l'utilisation d'expressions régulières parce qu'ils avaient entendu dire que les expressons réguliers n'étaient pas le bon outil pour le travail. Sauf hors-cours, ils ont continué en me demandant d'implémenter un moteur d'expression rationnelle
joojaa
1
@PaulDraper: Devinez ce que regex fait derrière la scène? il analyse la chaîne et stocke chaque élément jusqu'à ce qu'une correspondance de répétition possible se produise. C'est la même chose quel statet OP comme trop lent. donc juste parce qu'il s'agit d'un 2 liner, il n'y a pas de gain de performance.
dhein
2
@Zaibis, je serais normalement d'accord, mais c'est à la fois la solution la plus courte et la plus rapide ( stackoverflow.com/a/29482936/1212596) .... À l'exception de David, qui a été publiée après avoir fait ce commentaire. En fait, j'apprécie davantage l'approche de David (intelligente!).
Paul Draper
90

Vous pouvez faire l'observation que pour qu'une chaîne soit considérée comme répétitive, sa longueur doit être divisible par la longueur de sa séquence répétée. Étant donné que, voici une solution qui génère des diviseurs de la longueur de 1à n / 2inclus, divise la chaîne d'origine en sous-chaînes avec la longueur des diviseurs et teste l'égalité de l'ensemble de résultats:

from math import sqrt, floor

def divquot(n):
    if n > 1:
        yield 1, n
    swapped = []
    for d in range(2, int(floor(sqrt(n))) + 1):
        q, r = divmod(n, d)
        if r == 0:
            yield d, q
            swapped.append((q, d))
    while swapped:
        yield swapped.pop()

def repeats(s):
    n = len(s)
    for d, q in divquot(n):
        sl = s[0:d]
        if sl * q == s:
            return sl
    return None

EDIT: En Python 3, l' /opérateur a changé pour faire la division flottante par défaut. Pour obtenir la intdivision de Python 2, vous pouvez utiliser l' //opérateur à la place. Merci à @ TigerhawkT3 d'avoir porté cela à mon attention.

L' //opérateur effectue une division entière dans Python 2 et Python 3, j'ai donc mis à jour la réponse pour prendre en charge les deux versions. La partie où nous testons pour voir si toutes les sous-chaînes sont égales est maintenant une opération de court-circuit utilisant allet une expression de générateur.

MISE À JOUR: En réponse à une modification de la question d'origine, le code a maintenant été mis à jour pour renvoyer la plus petite sous-chaîne répétitive si elle existe et Nonesi elle n'existe pas. @godlygeek a suggéré d'utiliser divmodpour réduire le nombre d'itérations sur le divisorsgénérateur, et le code a également été mis à jour pour correspondre à cela. Il renvoie maintenant tous les diviseurs positifs de ndans l'ordre croissant, à l'exclusion de nlui - même.

Mise à jour supplémentaire pour des performances élevées: après plusieurs tests, je suis arrivé à la conclusion que le simple test d'égalité de chaîne a les meilleures performances de toute solution de découpage ou d'itérateur en Python. Ainsi, j'ai pris une feuille du livre de @ TigerhawkT3 et mis à jour ma solution. Il est maintenant plus de 6 fois plus rapide qu'auparavant, sensiblement plus rapide que la solution de Tigerhawk mais plus lent que celui de David.

Shashank
la source
3
Cette solution est incroyable. Vous pouvez modifier la méthode des diviseurs pour suivre le modèle produit-consommateur. Pour qu'il donne les résultats tels qu'ils sont trouvés. Ce sera dommage si ce n'est pas la meilleure réponse. Tout le reste est une force brute.
JustinDanielson
3
@JustinDanielson Il retourne un objet générateur créé à partir d'une expression de générateur, qui est un producteur implicite :) Il évaluera les diviseurs paresseux.
Shashank
1
Ohh. Je ne le savais pas. Eh bien, c'est encore mieux. : DI comprend pourquoi vous voulez éviter sqrt, mais vous pouvez utiliser n / 2 comme limite supérieure pour la plage de diviseurs.
JustinDanielson
1
@JustinDanielson Merci pour cette suggestion, la limite supérieure de la plage est désormais (n/2)incluse.
Shashank
1
Devrait n / 2en divisors()être n // 2?
TigerhawkT3
87

Voici quelques repères pour les différentes réponses à cette question. Il y a eu des résultats surprenants, notamment des performances très différentes selon la chaîne testée.

Certaines fonctions ont été modifiées pour fonctionner avec Python 3 (principalement en les remplaçant /par //pour assurer une division entière). Si vous voyez quelque chose de mal, que vous souhaitez ajouter votre fonction ou que vous souhaitez ajouter une autre chaîne de test, envoyez une requête ping à @ZeroPiraeus dans le salon de discussion Python .

En résumé: il y a environ 50 fois la différence entre les solutions les plus performantes et les moins performantes pour le grand ensemble d'exemples de données fournis par OP ici (via ce commentaire). La solution de David Zhang est clairement gagnante, surpassant toutes les autres d'environ 5 fois pour le grand ensemble d'exemples.

Deux ou trois des réponses sont très lentes dans des cas de non-correspondance extrêmement importants. Sinon, les fonctions semblent être également égales ou clairement gagnantes selon le test.

Voici les résultats, y compris les graphiques réalisés à l'aide de matplotlib et de seaborn pour montrer les différentes distributions:


Corpus 1 (exemples fournis - petit ensemble)

mean performance:
 0.0003  david_zhang
 0.0009  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0015  carpetpython
 0.0029  tigerhawk_1
 0.0031  davidism
 0.0035  saksham
 0.0046  shashank
 0.0052  riad
 0.0056  piotr

median performance:
 0.0003  david_zhang
 0.0008  zero
 0.0013  antti
 0.0013  tigerhawk_2
 0.0014  carpetpython
 0.0027  tigerhawk_1
 0.0031  davidism
 0.0038  saksham
 0.0044  shashank
 0.0054  riad
 0.0058  piotr

Graphique Corpus 1


Corpus 2 (exemples fournis - grand ensemble)

mean performance:
 0.0006  david_zhang
 0.0036  tigerhawk_2
 0.0036  antti
 0.0037  zero
 0.0039  carpetpython
 0.0052  shashank
 0.0056  piotr
 0.0066  davidism
 0.0120  tigerhawk_1
 0.0177  riad
 0.0283  saksham

median performance:
 0.0004  david_zhang
 0.0018  zero
 0.0022  tigerhawk_2
 0.0022  antti
 0.0024  carpetpython
 0.0043  davidism
 0.0049  shashank
 0.0055  piotr
 0.0061  tigerhawk_1
 0.0077  riad
 0.0109  saksham

Graphique Corpus 1


Corpus 3 (cas de bord)

mean performance:
 0.0123  shashank
 0.0375  david_zhang
 0.0376  piotr
 0.0394  carpetpython
 0.0479  antti
 0.0488  tigerhawk_2
 0.2269  tigerhawk_1
 0.2336  davidism
 0.7239  saksham
 3.6265  zero
 6.0111  riad

median performance:
 0.0107  tigerhawk_2
 0.0108  antti
 0.0109  carpetpython
 0.0135  david_zhang
 0.0137  tigerhawk_1
 0.0150  shashank
 0.0229  saksham
 0.0255  piotr
 0.0721  davidism
 0.1080  zero
 1.8539  riad

Graphique Corpus 3


Les tests et les résultats bruts sont disponibles ici .

davidisme
la source
37

Solution non regex:

def repeat(string):
    for i in range(1, len(string)//2+1):
        if not len(string)%len(string[0:i]) and string[0:i]*(len(string)//len(string[0:i])) == string:
            return string[0:i]

Solution non regex plus rapide, grâce à @ThatWeirdo (voir commentaires):

def repeat(string):
    l = len(string)
    for i in range(1, len(string)//2+1):
        if l%i: continue
        s = string[0:i]
        if s*(l//i) == string:
            return s

La solution ci-dessus est très rarement plus lente que l'original de quelques pour cent, mais elle est généralement beaucoup plus rapide - parfois beaucoup plus rapide. Il n'est toujours pas plus rapide que le davidisme pour les cordes plus longues, et la solution regex de zéro est supérieure pour les cordes courtes. Il sort le plus rapidement (selon le test du davidisme sur github - voir sa réponse) avec des chaînes d'environ 1000-1500 caractères. Quoi qu'il en soit, il est de manière fiable le deuxième plus rapide (ou mieux) dans tous les cas que j'ai testés. Merci, ThatWeirdo.

Tester:

print(repeat('009009009'))
print(repeat('254725472547'))
print(repeat('abcdeabcdeabcdeabcde'))
print(repeat('abcdefg'))
print(repeat('09099099909999'))
print(repeat('02589675192'))

Résultats:

009
2547
abcde
None
None
None
TigerhawkT3
la source
N'est-ce pas une solution de force brute?
JustinDanielson
7
@JustinDanielson Oui. Mais une solution néanmoins.
Sinkingpoint
3
Je vois environ 1e-5 à 3e-5 secondes pour les chaînes courtes, 3e-5 à 4e-5 secondes pour les chaînes longues réussies (1000 caractères), et un peu moins d'une milliseconde pour les chaînes longues infructueuses (pire cas) . Ainsi, mille chaînes de 1000 caractères prendraient environ une seconde. Comparé à la réponse mathématique, cela trouve les correspondances 10 fois plus rapides, mais prend 3 fois plus de temps pour échouer.
TigerhawkT3
repeat('aa')retoursNone
Tom Cornebize
2
len(string[0:i])est toujours égal à i(dans ce cas au moins). Le remplacement de ceux-ci, ainsi que l'enregistrement len(string)et les string[0:i]variables peuvent accélérer les choses. Aussi IMO, c'est une excellente solution, génial;)
ThatWeirdo
24

Tout d'abord, divisez la chaîne par deux tant qu'il s'agit d'un doublon en "2 parties". Cela réduit l'espace de recherche s'il y a un nombre pair de répétitions. Ensuite, en travaillant vers l'avant pour trouver la plus petite chaîne répétitive, vérifiez si le fractionnement de la chaîne complète par une sous-chaîne de plus en plus grande entraîne uniquement des valeurs vides. Seules les sous-chaînes jusqu'à length // 2doivent être testées, car tout ce qui se passerait n'aurait aucune répétition.

def shortest_repeat(orig_value):
    if not orig_value:
        return None

    value = orig_value

    while True:
        len_half = len(value) // 2
        first_half = value[:len_half]

        if first_half != value[len_half:]:
            break

        value = first_half

    len_value = len(value)
    split = value.split

    for i in (i for i in range(1, len_value // 2) if len_value % i == 0):
        if not any(split(value[:i])):
            return value[:i]

    return value if value != orig_value else None

Cela renvoie la correspondance la plus courte ou Aucune s'il n'y a pas de correspondance.

davidisme
la source
16

Le problème peut également être résolu O(n)dans le pire des cas avec la fonction préfixe.

Remarque, il peut être plus lent dans le cas général (UPD: et est beaucoup plus lent) que d'autres solutions qui dépendent du nombre de diviseurs de n, mais trouvent généralement échoue plus tôt, je pense que l'un des mauvais cas pour eux sera aaa....aab, où il y en a n - 1 = 2 * 3 * 5 * 7 ... *p_n - 1 a.

Tout d'abord, vous devez calculer la fonction de préfixe

def prefix_function(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    return pi

alors soit il n'y a pas de réponse, soit la période la plus courte est

k = len(s) - prefix_function(s[-1])

et il suffit de vérifier si k != n and n % k == 0(si k != n and n % k == 0alors la réponse est s[:k], sinon il n'y a pas de réponse

Vous pouvez vérifier la preuve ici (en russe, mais le traducteur en ligne fera probablement l'affaire)

def riad(s):
    n = len(s)
    pi = [0] * n
    for i in xrange(1, n):
        j = pi[i - 1]
        while(j > 0 and s[i] != s[j]):
            j = pi[j - 1]
        if (s[i] == s[j]):
            j += 1
        pi[i] = j;
    k = n - pi[-1]
    return s[:k] if (n != k and n % k == 0) else None
RiaD
la source
Votre prefix_function()n'est pas valide Python: vous avez manquantes sur vos deux points whileet ifdéclarations, et au &&lieu de and. Après avoir corrigé ceux-ci, il échoue à UnboundLocalError: local variable 'i' referenced before assignmentcause de la ligne for i in range(i, n):.
Zero Piraeus
Merci :-) Si vous pouvez mettre en place une fonction qui utilise votre prefix_function()pour renvoyer des résultats similaires aux autres réponses - soit la sous-chaîne la plus courte ou None- je vais l'inclure dans une référence révisée que je mets en place.
Zero Piraeus
@ZeroPiraeus, Cela fonctionne très bien en fait, je viens de l'appeler de manière incorrecte
RiaD
16

Cette version essaie uniquement les longueurs de séquence candidates qui sont des facteurs de la longueur de chaîne; et utilise l' *opérateur pour créer une chaîne complète à partir de la séquence candidate:

def get_shortest_repeat(string):
    length = len(string)
    for i in range(1, length // 2 + 1):
        if length % i:  # skip non-factors early
            continue

        candidate = string[:i]
        if string == candidate * (length // i):
            return candidate

    return None

Merci à TigerhawkT3 d'avoir remarqué que length // 2sans + 1ne correspondrait pas à l' ababaffaire.

Antti Haapala
la source
Cette solution est en effet pratiquement identique à ma solution optimisée. Je vois que vous avez une rangelimite de length//2, tout comme je l'ai fait - vous devez changer cela length//2+1si vous voulez attraper des chaînes qui sont exactement doublées (par exemple 'aabaab').
TigerhawkT3
Et maintenant, ils sont identiques! \ o / Je dois prêter plus d'attention à l'optimisation à l'avenir, mais je suis content que l'algorithme lui-même soit solide.
TigerhawkT3
15

Voici une solution simple, sans regex.

Pour les sous-chaînes de sdépart à partir de l'index zéro, de longueurs 1 à len(s), vérifiez si cette sous-chaîne substrest le motif répété. Cette vérification peut être effectuée en concaténant substravec elle-même les ratiotemps, de sorte que la longueur de la chaîne ainsi formée est égale à la longueur de s. Par conséquent ratio=len(s)/len(substr).

Renvoie la première fois qu'une telle sous-chaîne est trouvée. Cela fournirait la plus petite sous-chaîne possible, s'il en existe une.

def check_repeat(s):
    for i in range(1, len(s)):
        substr = s[:i]
        ratio = len(s)/len(substr)
        if substr * ratio == s:
            print 'Repeating on "%s"' % substr
            return
    print 'Non repeating'

>>> check_repeat('254725472547')
Repeating on "2547"
>>> check_repeat('abcdeabcdeabcdeabcde')
Repeating on "abcde"
Saksham Varma
la source
Maintenant que je regarde attentivement celle-ci, elle semble presque identique à ma solution initialement publiée (avant toute modification), avec les seules différences étant la sauvegarde de la longueur et de la sous-chaîne. Je suppose que j'avais un assez bon algorithme. : P
TigerhawkT3
@ TigerhawkT3 Ouais en effet! :)
Saksham Varma
9

J'ai commencé avec plus de huit solutions à ce problème. Certains étaient basés sur l'expression régulière (correspondance, findall, split), certains de découpage et de test de chaînes, et certains avec des méthodes de chaîne (find, count, split). Chacun avait des avantages en termes de clarté de code, de taille de code, de vitesse et de consommation de mémoire. J'allais poster ma réponse ici quand j'ai remarqué que la vitesse d'exécution était classée comme importante, j'ai donc fait plus de tests et d'amélioration pour arriver à ceci:

def repeating(s):
    size = len(s)
    incr = size % 2 + 1
    for n in xrange(1, size//2+1, incr):
        if size % n == 0:
            if s[:n] * (size//n) == s:
                return s[:n]

Cette réponse semble similaire à quelques autres réponses ici, mais elle a quelques optimisations de vitesse que d'autres n'ont pas utilisées:

  • xrange est un peu plus rapide dans cette application,
  • si une chaîne d'entrée est de longueur impaire, ne vérifiez aucune sous-chaîne de longueur paire,
  • en utilisant s[:n]directement, nous évitons de créer une variable dans chaque boucle.

Je serais intéressé de voir comment cela fonctionne dans les tests standard avec du matériel commun. Je pense qu'il sera bien en deçà de l'excellent algorithme de David Zhang dans la plupart des tests, mais devrait être assez rapide sinon.

J'ai trouvé ce problème très contre-intuitif. Les solutions que je pensais rapides seraient lentes. Les solutions qui paraissaient lentes étaient rapides! Il semble que la création de chaînes de Python avec l'opérateur multiply et les comparaisons de chaînes soient hautement optimisées.

Logic Knight
la source
Pas mal du tout :-) Le benchmark fonctionne sur Python 3.4 (en partie parce que OP ne spécifie pas de version et c'est ce que tout le monde devrait utiliser, et en partie parce qu'il utilise le nouveau statisticsmodule), j'ai donc dû changer votre /s en //s et remplacez xrange()par range()(qui se comporte comme 2.x xrange()dans 3.x).
Zero Piraeus
Voici les révisions de l'indice de référence, vous pouvez donc revoir mes modifications, soit dit en passant.
Zero Piraeus
Merci Zero. C'était rapide. Les résultats ont légèrement baissé par rapport à mes prévisions. Je soupçonne que les techniques que j'ai utilisées pour la vitesse dans Python 2.7 ne sont pas très efficaces dans Python 3.4. Oh, eh bien - un exercice amusant et éducatif.
Logic Knight
//dans 3.x est une division entière (tout comme le comportement 2.x de /), tandis que 3.x /est une division flottante (qui, j'en suis sûr, serait beaucoup plus lente même si elle ne cassait pas votre solution en provoquant une tentative d'utilisation) un flotteur comme index). Comme mentionné, 3.x range()est la même chose que 2.x xrange(); aucun équivalent de 2.x range()n'existe dans 3.x. Je ne pense donc pas que ce soit la cause de tout écart entre l'indice de référence et les délais que vous avez faits. C'est probablement juste que 3.x est globalement plus lent que 2.x (ou peut-être que votre machine est plus rapide que la mienne).
Zero Piraeus
Quand j'aurai un peu de temps, j'examinerai de près les différences d'exécution entre Python 2 et Python 3.
Logic Knight
2

Cette fonction s'exécute très rapidement (testée et c'est plus de 3 fois plus rapide que la solution la plus rapide ici sur des chaînes avec plus de 100k caractères et la différence s'accentue plus le motif répétitif est long). Il essaie de minimiser le nombre de comparaisons nécessaires pour obtenir la réponse:

def repeats(string):
    n = len(string)
    tried = set([])
    best = None
    nums = [i for i in  xrange(2, int(n**0.5) + 1) if n % i == 0]
    nums = [n/i for i in nums if n/i!=i] + list(reversed(nums)) + [1]
    for s in nums:
        if all(t%s for t in tried):
            print 'Trying repeating string of length:', s
            if string[:s]*(n/s)==string:
                best = s
            else:
                tried.add(s)
    if best:
        return string[:best]

Notez que par exemple pour une chaîne de longueur 8, il ne vérifie que les fragments de taille 4 et il n'a pas besoin de tester davantage car le motif de longueur 1 ou 2 entraînerait la répétition du motif de longueur 4:

>>> repeats('12345678')
Trying repeating string of length: 4
None

# for this one we need only 2 checks 
>>> repeats('1234567812345678')
Trying repeating string of length: 8
Trying repeating string of length: 4
'12345678'
Piotr Dabkowski
la source
Merci :) Je ne l'ai cependant pas beaucoup optimisé. Je voulais juste présenter une approche différente parce que d'autres réponses se concentrent sur la recherche du modèle et mon approche vise à prouver qu'il n'y a pas de modèle :) Par conséquent, pour les chaînes aléatoires, mon algorithme devrait fonctionner beaucoup plus rapidement.
Piotr Dabkowski
0

Dans la réponse de David Zhang, si nous avons une sorte de tampon circulaire, cela ne fonctionnera pas: en principal_period('6210045662100456621004566210045662100456621')raison du démarrage 621, où j'aurais aimé qu'il crache:00456621 .

En étendant sa solution, nous pouvons utiliser les éléments suivants:

def principal_period(s):
    for j in range(int(len(s)/2)):
        idx = (s[j:]+s[j:]).find(s[j:], 1, -1)
        if idx != -1:
            # Make sure that the first substring is part of pattern
            if s[:j] == s[j:][:idx][-j:]:
                break

    return None if idx == -1 else s[j:][:idx]

principal_period('6210045662100456621004566210045662100456621')
>>> '00456621'
sachinruk
la source
-1

Voici le code en python qui vérifie la répétition de la sous-chaîne dans la chaîne principale donnée par l'utilisateur .

print "Enter a string...."
#mainstring = String given by user
mainstring=raw_input(">")
if(mainstring==''):
    print "Invalid string"
    exit()
#charlist = Character list of mainstring
charlist=list(mainstring)
strarr=''
print "Length of your string :",len(mainstring)
for i in range(0,len(mainstring)):
    strarr=strarr+charlist[i]
    splitlist=mainstring.split(strarr)
    count = 0
    for j in splitlist:
        if j =='':
            count+=1
    if count == len(splitlist):
        break
if count == len(splitlist):
    if count == 2:
        print "No repeating Sub-String found in string %r"%(mainstring)

    else:
        print "Sub-String %r repeats in string %r"%(strarr,mainstring)
else :
    print "No repeating Sub-String found in string %r"%(mainstring)

Entrée :

0045662100456621004566210045662100456621

Sortie :

Longueur de votre chaîne: 40

La sous-chaîne '00456621' se répète dans la chaîne '0045662100456621004566210045662100456621'

Entrée :

004608294930875576036866359447

Sortie :

Longueur de votre chaîne: 30

Aucune sous-chaîne répétée trouvée dans la chaîne '004608294930875576036866359447'

Srivishnu
la source