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