adplus-dvertising

Décomposition de phrases à partir d'un dictionnaire - Programmation compétitive

Décomposition de phrases à partir d'un dictionnaire - Programmation compétitive

Mostafa veut initier ses élèves à la traduction par une méthode simple et naïve qui est basée sur la décomposition de la phrase donnée en mots puis la traduction de chaque mot séparément et enfin la traduction de la phrase entière. Pour simplifier la traduction, Mostafa doit donner à ses élèves uniquement des phrases réalisables (phrases qui peuvent être construites à partir du dictionnaire) étant donné un dictionnaire de tous les mots possibles.

Le problème est que la phrase est sans espace, ce qui signifie qu'il n'y a pas d'espace entre les mots.

Aidez Mostafa en écrivant un programme qui détermine si la phrase donnée peut être construite à partir du dictionnaire donné.

Entrée

La première ligne contient la phrase. La deuxième ligne contient tous les mots du dictionnaire.

Sortie

Oui si la phrase peut être construite à partir du dictionnaire donné. Non, sinon.

  Exemples
Entrée du programmeSortie du programme
meknesestunebellevilleaumaroc
meknes fes marrakech ville maroc une est belle magnifique historique imperiale au
Oui
agadirestlacapitaledumaroc
meknes fes marrakech ville maroc une est belle magnifique historique imperiale au
Non

Solution 1 (récursive)

L'idée est simple, nous considérons chaque préfixe et le recherchons dans le dictionnaire. Si le préfixe est présent dans le dictionnaire, nous recherchons le reste de la chaîne (ou suffixe).

Si l'appel récursif pour le suffixe retourne vrai, nous retournons vrai, sinon nous essayons le préfixe suivant. Si nous avons essayé tous les préfixes et qu'aucun d'entre eux n'a donné de solution, nous retournons Non.

#include <iostream>
#include <string>
#include <set>
#include <sstream>

using namespace std;

bool estvalide(string phrase, const set<string> &dictionnaire){
    int n=phrase.size();
    if(n==0)
        return true;
    
    for(int i=1; i < n+1; i++){
        if(dictionnaire.count(phrase.substr(0, i))>0  && estvalide(phrase.substr(i,n-i),dictionnaire))
            return true;
    }
    return false;
}

int main()
{
    string phrase, mots;
    set<string> dictionnaire;

    cin >> phrase;

    // Sauter tous les espaces blancs de tête pour éviter le conflit avec getline
    std::cin >> std::ws;

    getline(cin,mots);
    std::istringstream split(mots);
    for (string mot; getline(split, mot, ' '); dictionnaire.insert(mot));

    if(estvalide(phrase, dictionnaire))
        cout << "Oui";
    else
        cout << "Non";
    
    return 0;
}
                    
import sys

def estvalide(phrase):

    global dictionnaire
 
    n = len(phrase)
 
    if (n == 0):
        return True
 
    for i in range(1,n + 1):

        if (phrase[0:i] in dictionnaire and estvalide(phrase[i: n])):
            return True
 
    return False


phrase=sys.stdin.readline().strip()

dictionnaire=set(map(str, sys.stdin.readline().strip().split()))


if estvalide(phrase):
    print("Oui")
else:
    print("Non")
                    

Solution 2 (Programmation dynamique)

Le problème ci-dessus présente des sous-problèmes qui se chevauchent. Nous pouvons donc résoudre le problème en utilisant la programmation dynamique

#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <sstream>

using namespace std;

bool estvalide(string phrase, const set<string> &dictionnaire){
    int n=phrase.size();
    if(n==0)
        return true;
    
    // La valeur decomp[i] sera True si la phrase[0..i-1] peut être segmentée en mots du dictionnaire, 
    // sinon False.
    bool decomp[n+1];
    memset(decomp, false, n+1);

    for(int i=1; i < n+1; i++){
        if(dictionnaire.count(phrase.substr(0, i))>0  && decomp[i]==false)
            decomp[i]=true;
        
        // decomp[i] est vrai, puis vérifie toutes les sous-chaînes à partir du (i+1)ème caractère et stocke leurs résultats.
        if(decomp[i]==true){

            // Si nous avons atteint le dernier préfixe
            if (n==i)
                return true;
            
            for(int j=i+1; j < n+1; j++){
                if(dictionnaire.count(phrase.substr(i, j-i))>0  && decomp[j]==false)
                    decomp[j]=true;
                
                // Si nous avons atteint le dernier caractère
                if (j == n && decomp[j] == true)
                    return true;
            }

                
        }
    }
    // Si nous avons essayé tous les préfixes et qu'aucun d'entre eux n'a fonctionné.
    return false;
}

int main()
{
    string phrase, mots;
    set<string> dictionnaire;

    cin >> phrase;

    // Sauter tous les espaces blancs de tête pour éviter le conflit avec getline
    std::cin >> std::ws;

    getline(cin,mots);
    std::istringstream split(mots);
    for (string mot; getline(split, mot, ' '); dictionnaire.insert(mot));

    if(estvalide(phrase, dictionnaire))
        cout << "Oui";
    else
        cout << "Non";
    
    return 0;
}
                    
import sys

def estvalide(phrase):
    global dictionnaire
    n=len(phrase)

    if n==0:    return True

    # La valeur decomp[i] sera True si la phrase[0..i-1] peut être segmentée en mots du dictionnaire, 
    # sinon False.
    decomp = [ False for _ in range(n+1) ]

    for i in range(1,n+1):
        if (phrase[0:i] in dictionnaire and decomp[i]==False):
            decomp[i]=True
        
        # decomp[i] est vrai, puis vérifie toutes les sous-chaînes à partir du (i+1)ème caractère et stocke leurs résultats.
        if(decomp[i]==True):
            
            # Si nous avons atteint le dernier préfixe
            if i==n:
                return True
            
            for j in range(i+1,n+1):
                if (phrase[i:j] in dictionnaire and decomp[j]==False):
                    decomp[j]=True
                
                # Si nous avons atteint le dernier caractère
                if (j == n and decomp[j] == True):
                    return True
    
    # Si nous avons essayé tous les préfixes et qu'aucun d'entre eux n'a fonctionné.
    return False


phrase=sys.stdin.readline().strip()

dictionnaire=set(map(str, sys.stdin.readline().strip().split()))

if estvalide(phrase):
    print("Oui")
else:
    print("Non")
                    

Partager ce cours avec tes amis :
Rédigé par ESSADDOUKI Mostafa
ESSADDOUKI
The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.