GCD strings

Question 1

Que cherche-t-on dans un problème de type “GCD of Strings” ?

Answer 1

On cherche la plus longue chaîne qui peut être répétée plusieurs fois pour former chacune des deux chaînes données.

Question 2

Quelle est la première vérification à faire avant de calculer quoi que ce soit ?

Answer 2

Vérifier si str1 + str2 == str2 + str1.
Si ce n’est pas le cas, aucun motif commun n’existe.

Question 3

Pourquoi vérifier str1 + str2 == str2 + str1 ?

Answer 3

Parce que si deux chaînes sont formées par la répétition d’un même motif, leur concaténation dans n’importe quel ordre donne le même résultat.

Question 4

Comment trouve-t-on la taille du motif commun si la concaténation est valide ?

Answer 4

On prend le PGCD (GCD) des longueurs de str1 et str2.
Le motif commun sera str1[:gcd(len(str1), len(str2))].

Question 5

Quelle est la formule utilisée pour calculer le PGCD (GCD) ?

Answer 5

On utilise l’algorithme d’Euclide

Question 6

Quelle est la complexité en temps de cette méthode ?

Answer 6

Calcul du GCD : O(log(min(len(str1), len(str2))))

Concaténations et comparaisons : O(len(str1) + len(str2))

Question 7

Comment généraliser ce pattern à d’autres problèmes ?

Answer 7

Ce pattern s’applique dès qu’on doit trouver une structure commune en répétition et qu’on peut représenter le problème par la taille (longueur, nombre d’éléments, etc.).