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 programme | Sortie 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")