Défi N°6 : Les palindromes
Bonjour,
Pour ce sixième défi proposé par SpiceGuid, l'équipe de developpez.com vous propose un challenge assez court qui peut laisser place à l'optimisation.
Challenge :
Il s'agit d'écrire une fonction (s: string) → string qui renvoie un palindrome p tel que:
- s contient p
- s ne contient aucun palindrome qui soit strictement plus long que p
On rappelle qu'un palindrome est une chaîne de caractère dont l'ordre de lettre est identique, selon que la lise par la gauche ou par la droite.
Formellement, une chaîne s est un palindrome si et seulement si :
Pour tout i de 0 à taille(s)-1, s[i] = s[taille(s)-1-i]
Les règles
Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :
- la maintenabilité
- la simplicité
- le fait qu'il soit optimisé
Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.
Pour répondre, il vous suffit de poster à la suite.
A vos claviers
:merci: de votre participation.
__________________________
Sujet proposé par SpiceGuid
Une methode utilisant des hachages
Il me semble que ton algo est O( n * p ) , mais ou p se serait la moyenne de la taille des palindromes et non que celle du plus grand ( ce qui est la meme chose qu'en pire cas ... )
Enfin ...
je vous propose un algo qui n'est pas mieux que les votre dans le cas moyen parce qu'il a une constante un peu plus grande que les votre et qu'il n'est qu'en O( n * log(Pmax) ) (en pire cas comme en moyenne ) or je crois que Pmoyen ~= log(Pmax) sur une distribution bien aleatoire donc pas bien mieux ... sauf sur le pire cas !
Le principe de cet algo repose sur le fait que si il n'existe pas de palindrome de taille n ou n+1 (eh oui obliger de distinguer les cas pair et impair ) c'est qu'alors il n'y en a pas de plus grand que n. De la on peut faire une dichotomie.
La fonction qui regarde si il n'y a pas de palindrome fonctionne avec un hachage ce qui permet ( globalement ) de considerer que la comparaison des cotes gauches et droites se fait en O(1) si elle echoue et O(P) si elle reussit comme elle ne reussit que une fois par appel on a bien du O(N) pour cette fonction donc un total de O( N ln P ).
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91
|
class palindrome
{
public:
int debut , plus_grand ;
private:
int * hash_droite ;
const char * source ;
int longueur;
inline bool compare ( int taille , int a ,int b )
{
while ( taille > 0 )
{
if( source[a--] != source[b++] )
return false ;
taille--;
}
return true ;
}
inline bool possible ( const int taille )
{
plus_grand = -1 ;
int decal = 1 ;
for ( int i = 0 ; i < taille ; i++ )
decal *= 5 ;
int hash = 0 ;
hash_droite[ longueur-1 ] = source[ longueur - 1 ] ;
for( int i = longueur-2 ; i >= 0; i -- )
if ( (size_t)i+taille < longueur )
hash_droite[ i ] = hash_droite[i+1]*5 + source[i] - decal*source[i+taille] ;
else
hash_droite[ i ] = hash_droite[i+1]*5 + source[i] ;
for ( int i = 0 ; i < taille ; i ++ )
hash = hash * 5 + source[i] ;
for ( size_t i = taille ; i + taille <= longueur ; i++ )
{
if( i+taille < longueur )
if( hash_droite[i+1] == hash )
if ( compare ( taille, i-1 , i+1 ) )
{
plus_grand = 2*taille+1 ;
debut = i-taille ;
return true ;
}
if( hash_droite[i] == hash )
if ( compare ( taille, i-1 , i ) )
{
plus_grand = 2*taille+1 ;
debut = i-taille ;
}
hash = hash*5+source[i]-decal*source[i-taille] ;
}
return plus_grand != -1 ;
}
public:
palindrome ( const string & chaine )
{
plus_grand = -1 ;
source = chaine.c_str() ;
longueur = chaine.size () ;
hash_droite = new int[ longueur ] ;
int gauche = 1 ;
int droite = longueur/2+1 ;
while( gauche < droite && possible( gauche ) )
gauche *= 2 ;
droite = min( droite , gauche );
gauche /= 2 ;
while ( droite-gauche > 1 )
{
const int milieu = (droite+gauche)/2 ;
if ( possible ( milieu ) )
gauche = milieu ;
else
droite = milieu ;
}
possible(gauche);
delete hash_droite ;
}
}; |
Voila!
Louis