DddddélMMMMMM Emul comprisdMMMMMMdiceTdMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM

L'idée du code ci-dessous est de considérer les sous-chaînes de toutes les longueurs; la chaîne d'origine peut être divisée de façon égale et vérifier si elles se répètent sur la chaîne d'origine. Une méthode simple consiste à vérifier tous les diviseurs de la longueur de 1 à la racine carrée de la longueur. Ce sont des diviseurs si la division produit un nombre entier, qui est également un diviseur complémentaire. Par exemple, pour une chaîne de longueur 100, les diviseurs sont 1, 2, 4, 5, 10 et les diviseurs complémentaires sont 100 (pas utile en longueur de sous-chaîne car la sous-chaîne apparaîtra une seule fois), 50, 25, 20 (et 10 , Que nous avons déjà trouvé).

 function substr_repeats(str, sublen, subcount) { for (var c = 0; c < sublen; c++) { var chr = str.charAt(c); for (var s = 1; s < subcount; s++) { if (chr != str.charAt(sublen * s + c)) { return false; } } } return true; } function is_periodic(str) { var len = str.length; if (len < 2) { return false; } if (substr_repeats(str, 1, len)) { return true; } var sqrt_len = Math.sqrt(len); for (var n = 2; n <= sqrt_len; n++) { // n: candidate divisor var m = len / n; // m: candidate complementary divisor if (Math.floor(m) == m) { if (substr_repeats(str, m, n) || n != m && substr_repeats(str, n, m)) { return true; } } } return false; } 

Malheureusement, il n'y a pas de méthode String pour comparer une sous-chaîne d'une autre chaîne (par exemple, en langage C qui serait strncmp(str1, str2 + offset, length) ).

Dites que votre chaîne a une longueur de 120 et consiste en une sous-chaîne de longueur 6 répétée 20 fois. Vous pouvez le regarder également comme étant constitué d'une sous-longueur (longueur de la sous-chaîne) 12 répétées 10 fois, de la subdivision 24 répétée 5 fois, de la décompression 30 répétée 4 fois ou de la sublimération 60 répétée 2 fois (les subdivisions sont données par les facteurs primaires de 20 (2 * 2 * 5) appliqué dans différentes combinaisons à 6). Maintenant, si vous vérifiez si votre chaîne contient une requête de 60 fois répétée 2 fois et que la vérification échoue, vous pouvez également être sûr qu'elle ne contiendra aucune sous-partition qui est un diviseur (c'est-à-dire une combinaison de facteurs principaux) de 60 , Y compris 6. En d'autres termes, de nombreux contrôles effectués par le code ci-dessus sont redondants. Par exemple, dans le cas de la longueur 120, le code ci-dessus vérifie (heureusement en retard rapidement la plupart du temps) les subdivisions suivantes: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60 (dans cet ordre: 1, 60, 2, 40, 3, 30, 4, 24, 5, 20, 6, 15, 8, 12, 10). Parmi ceux-ci, seuls les éléments suivants sont nécessaires: 24, 40, 60. Il s'agit de 2 * 2 * 2 * 3, 2 * 2 * 2 * 5, 2 * 2 * 3 * 5, c'est-à-dire les combinaisons de primes de 120 ( 2 * 2 * 2 * 3 * 5) avec l'une de chaque prime (non répétation) retirée, ou, si vous le préférez, 120/5, 120/3, 120/2. Ainsi, en oubliant pour un instant que la factorisation primitive efficace n'est pas une tâche simple, nous pouvons restreindre nos contrôles des sous-chaînes répétitives aux sous-chaînes p de longueur de longueur / p, où p est un facteur de longueur premier. Voici la plus simple implémentation non triviale:

 function substr_repeats(str, sublen, subcount) { see above } function distinct_primes(n) { var primes = n % 2 ? [] : [2]; while (n % 2 == 0) { n /= 2; } for (var p = 3; p * p <= n; p += 2) { if (n % p == 0) { primes.push(p); n /= p; while (n % p == 0) { n /= p; } } } if (n > 1) { primes.push(n); } return primes; } function is_periodic(str) { var len = str.length; var primes = distinct_primes(len); for (var i = primes.length - 1; i >= 0; i--) { var sublen = len / primes[i]; if (substr_repeats(str, sublen, len / sublen)) { return true; } } return false; } 

Essayant ce code sur mon PC Linux J'ai eu une surprise: sur Firefox, c'était beaucoup plus rapide que la première version, mais sur Chromium, il était plus lent, devenant plus rapide que pour les chaînes avec des longueurs de milliers. Enfin, j'ai découvert que le problème était lié au tableau que distinct_primes() crée et passe à is_periodic() . La solution était de se débarrasser du tableau en fusionnant ces deux fonctions. Le code est ci-dessous et les résultats des tests sont sur http://jsperf.com/periodic-strings-1/5

 function substr_repeats(str, sublen, subcount) { see at top } function is_periodic(str) { var len = str.length; var n = len; if (n % 2 == 0) { n /= 2; if (substr_repeats(str, n, 2)) { return true; } while (n % 2 == 0) { n /= 2; } } for (var p = 3; p * p <= n; p += 2) { if (n % p == 0) { if (substr_repeats(str, len / p, p)) { return true; } n /= p; while (n % p == 0) { n /= p; } } } if (n > 1) { if (substr_repeats(str, len / n, n)) { return true; } } return false; } 

N'oubliez pas que les délais collectés par jsperf.org sont absolus et que différents expérimentateurs avec différentes machines contribueront à différentes combinaisons de chaînes. Vous devez modifier une nouvelle version privée de l'expérience si vous souhaitez comparer efficacement deux moteurs JavaScript.

Une option est de continuer à utiliser un regex, mais pour devenir gourmand en déposant le ? :

 /^(.+)\1+$/ 

Selon les chaînes d'entrée exactes, cela peut réduire la quantité de backtrack requise et accélérer la correspondance.

Si une chaîne est périodique:

• Le dernier élément serait également le dernier élément de la période
• La durée de la période diviserait la longueur de la chaîne

Nous pouvons donc créer un algorithme super gourmand qui prend le dernier élément et vérifie les occurrences jusqu'à la moitié de la longueur. Lorsque nous en trouvons un, nous vérifions si la longueur de la sous-chaîne divise la longueur principale et seulement après cela, nous testons contre la chaîne.

 function periodic(str){ for(var i=0; i<=str.length/2; i++){ if(str[i] === str[str.length-1] && str.length%(i+1) === 0){ if (str.substr(0,i+1).repeat(str.length/(i+1)) === str){ return true; } } } return false; } 

Il y a une réponse qui mérite d'être mentionnée pour sa pure beauté. Ce n'est pas à moi, je l'ai simplement adapté à partir de la version Python, qui est ici: Comment puis-je savoir si une chaîne se répète dans Python?

 function is_periodic(s) { return (s + s.substring(0, s.length >> 1)).indexOf(s, 1) > 0; } 

Malheureusement, la vitesse n'est pas à la hauteur de la beauté (et aussi la beauté a subi un peu l'adaptation de Python, puisque indexOf() a un paramètre de départ, mais pas un paramètre d'arrêt). Une comparaison avec la (les) solution (s) regex et avec les fonctions de mon autre réponse est ici . Même avec des cordes de longueur aléatoire dans [4, 400] basées sur un petit alphabet de 4 caractères, les fonctions de mon autre réponse sont meilleures. Cette solution est cependant plus rapide que la (les) solution (s) regex.

Cette solution pourrait être appelée «solution phasehift» . La chaîne est traitée comme une onde identique à elle-même lors du déplacement de sa phase.

L'avantage de cette solution par rapport à ceux de mon autre réponse est qu'il peut être facilement adapté pour renvoyer la sous-chaîne répétitive la plus courante, comme ceci:

 function repeating_substr(s) { period = (s + s.substring(0, s.length >> 1)).indexOf(s, 1); return period > 0 ? s.substr(0, period) : null; } 

Une approche directe consiste à diviser la chaîne en morceaux de taille égale et à tester si chaque mandrin est identique au premier morceau. Voici un algorithme en augmentant la taille du morceau de 1 à la longueur / 2, en ignorant les tailles de morceaux qui ne divisent pas la longueur.

 function StringUnderTest (str) { this.str = str; this.halfLength = str.length / 2; this.period = 0; this.divideIntoLargerChunksUntilPeriodicityDecided = function () { this.period += 1; if (this.period > this.halfLength) return false; if (this.str.length % this.period === 0) if (this.currentPeriodOk()) return true; return this.divideIntoLargerChunksUntilPeriodicityDecided(); }; this.currentPeriodOk = function () { var patternIx; var chunkIx; for (chunkIx=this.period; chunkIx<this.str.length; chunkIx+=this.period) for (patternIx=0; patternIx<this.period; ++patternIx) if (this.str.charAt(patternIx) != this.str.charAt(chunkIx+patternIx)) return false; return true; }; } function isPeriodic (str) { var s = new StringUnderTest(str); return s.divideIntoLargerChunksUntilPeriodicityDecided(); } 

Je n'ai pas testé la vitesse, cependant …