Facteurs

Définition

Pour un mot donné m, on appelle facteur de m tout mot apparaissant dans m.

Exemples:

• Les facteurs du mot "NSI" sont N, S, I, NS, SI, NSI (et le mot vide).
• Les facteurs du mot "carambar": c, a, r, m, b, ca, ar, ra, am, mb, ba, car, ara, ram, amb, mba, bar, cara, aram, ramb, amba, mbar, caram, aramb, ramba, ambar, caramb, aramba, rambar, caramba, arambar, carambar (et le mot vide).

Un facteur du mot m est donc un mot dont les lettres sont des lettres consécutives du mot m.

Exercice 1

Écrire un code possible pour la fonction suivante:

def facteur(mot, début, longueur):
    """
    mot -- chaîne de caractères
    début -- entier entre 0 et len(mot)-1
    longueur -- entier entre 1 et len(mot) 

    renvoie le facteur de mot commençant au caractère
    d'indice  début et comportant longueur caractères

    >>> facteur('carambar', 2,4)
    'ramb'
    """

Un code

def facteur(mot, début, longueur):
    """
    mot -- chaîne de caractères
    début -- entier entre 0 et len(mot)-1
    longueur -- entier entre 1 et len(mot) 

    renvoie le facteur de mot commençant au caractère
    d'indice  début et comportant longueur caractères

    >>> facteur('carambar', 2,4)
    'ramb'
    """
    assert 0 <= début < len(mot), f"{début} n'est pas un indice de la chaîne {mot}."
    assert 0 < longueur <= len(mot), f"Un facteur, non vide, a une longueur entre 1 et {len(mot)}."
    fact = ''
    for k in range(début, début + longueur):
        fact = fact + mot[k]
    return fact

Exercice 2

Écrire un code possible pour la fonction suivante:

def facteurs(mot, n):
    """
    mot -- chaine de caractères
    n -- entier naturel > 0

    renvoie une chaîne constituée des facteurs 
    de mot ayant longueur n,
    séparés par une virgule
    (certains facteurs peuvent éventuellement être répétés)

    >>> facteurs('carambar', 3)
    'car,ara,ram,amb,mba,bar'
    """

Un code

On utilise la fonction facteur de l'exercice précédent.

def facteurs(mot, n):
    """
    mot -- chaine de caractères
    n -- entier naturel > 0

    renvoie une chaîne constituée des facteurs 
    de mot ayant longueur n,
    séparés par une virgule
    (certains facteurs peuvent éventuellement être répétés)

    >>> facteurs('carambar', 3)
    'car,ara,ram,amb,mba,bar'
    """
    assert n > 0, "n doit être >0."
    assert n <= len(mot), "n ne peut être supérieur à len(mot)."
    ch = facteur(mot, 0, n)
    for k in range(1, len(mot)-n+1):
        ch = ch + ',' + facteur(mot, k, n)
    return ch

Exercice 3

Écrire un code possible pour la fonction suivante:

def facteur_commun_longueur(mot1, mot2, lg):
    """
    mot1 -- de type string
    mot2 -- de type string
    lg -- entier > 0

    renvoie un facteur commun à mot1 et mot2, de longueur n.
    renvoie la chaîne vide si un tel facteur n'existe pas.

    >>> facteur_commun_longueur('marcel', 'marcelle', 6)
    'marcel'
    """

Un code

On utilise la fonction facteur de l'exercice précédent.

def facteur_commun_longueur(mot1, mot2, lg):
    """
    mot1 -- de type string
    mot2 -- de type string
    lg -- entier > 0

    renvoie un facteur commun à mot1 et mot2, de longueur n.
    renvoie la chaîne vide si un tel facteur n'existe pas.

    >>> facteur_commun_longueur('marcel', 'marcelle', 6)
    'marcel'
    >>> facteur_commun_longueur('carambar', 'johnrambo', 4)
    'ramb'
    >>> facteur_commun_longueur('carambar', 'johnrambo', 2)
    'ra'
    """
    for i in range(0, len(mot1)-lg+1):
        for j in range(0, len(mot2)-lg+1):
            fact = facteur(mot1, i, lg)
            if fact == facteur(mot2, j, lg):
                return fact
    return ''

Exercice 4

Écrire un code possible pour la fonction suivante:

def facteur_commun(mot1, mot2):
    """
    mot1 -- de type string
    mot2 -- de type string

    renvoie, parmi les facteurs communs à mot1 et mot2, le plus long.
    renvoie la chaîne vide s'il n'y a pas de tel facteur.

    >>> facteur_commun('carambar', 'johnrambo')
    'ramb'
    >>> facteur_commun('Je suis ton père', 'bazooka')
    'o'
    >>> facteur_commun('Un Anneau pour les amener tous et dans les ténèbres les lier.', 'kzyk')
    ''
    """

Un code

On utilise la fonction facteur_commun_longueur de l'exercice précédent.

def facteur_commun(mot1, mot2):
    """
    mot1 -- de type string
    mot2 -- de type string

    renvoie, parmi les facteurs communs à mot1 et mot2, le plus long.
    renvoie la chaîne vide s'il n'y a pas de tel facteur.

    >>> facteur_commun('carambar', 'johnrambo')
    'ramb'
    >>> facteur_commun('Je suis ton père', 'bazooka')
    'o'
    >>> facteur_commun('Un Anneau pour les amener tous et dans les ténèbres les lier.', 'kzyk')
    ''
    """
    # un préfixe commun ne peut dépasser la longueur
    # du plus court des deux mots:
    taille = min(len(mot1), len(mot2))

    for k in range(taille, 0, -1):
        fact = facteur_commun_longueur(mot1, mot2, k)
        if fact != '':
            return fact

    return ''