Discussion :

[Woodgate]

Bonjour,

J'ai un petit problème avec un script que je dois réaliser. Je souhaiterais compter le nombre de palindromes possibles dans une chaine, mais je ne dois compter que les palindromes maximums.

C'est à dire que la chaine "ababab" contient deux palindromes maximums : "ababa" et "babab", mais "aba" et "bab" n'en font pas partie.

J'ai réalisé ce script, mais il ne fonctionne pas correctement (je me retrouve parfois avec trop de résultats, et parfois avec pas assez).

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
<?php
function palindromes(){
 
	$palindromes = 0;
	$chaine_finale = "";
 
	$som = 0;
	$args = func_get_args();
	$nbr = count($args);
 
 
	for($i=0;$i<$nbr;++$i){
 
 
		$args[$i] = strtolower(trim($args[$i]));
 
		$chaine_finale = $chaine_finale . $args[$i];
 
	}
 
 
	$caracteres = strlen($chaine_finale);
	$half = ceil($caracteres / 2);
 
	for($i=1;$i<$caracteres-1;$i++){
 
		if($i<$half){
		$limit = $i;
		}
		elseif($i>=$half){
		$limit = $caracteres - $i - 1;
		}
 
		$j = 0;
		$k = 0;
 
		while($j<$limit AND $k==0){
 
			$j++;
 
			$mot = substr($chaine_finale,$i-$j,$j+$j+1);
 
			echo "$i - $j (Test de $mot)<br/>";
 
		}
 
		echo "<br/><br/>";
 
	}
 
	echo "<b>Nombre de palindromes :</b> $palindromes";
 
}
 
palindromes("ababab");
?>

Si quelqu'un à une idée... merci !

[SpaceFrog]

perso j'aurais coupé en deux , fait un strrev sur la seconde partie et testé l'égalité ...
faut juste tester si la longueur est paire ou non ...
a ce moment faudra faire du substring debut mileu fin et tester debut=strrev(fin)

[SpaceFrog]

ou encore beaucoup plus simple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

if($chaine==strrev($chaine))

[guidav]

C'est bien plus compliqué que ça : il s'git de repérer les palindromes dans une chaîne, mais il peut y en avoir plusieurs.
Question : dans "abccbaazertybccb", faut-il compter 2 palindromes (abccba et bccb) ou considère-ton que bccb est contenu dans abccba ?
Ca influe sur l'algorithme, mais dans les 2 cas il y a une méthode facile et fastidieuse.

[SpaceFrog]

ben ce n'est pas ce que j'ai compris dasn ses explications ...
il parlait uniquement de palindrome principal et pas de sous palindormes non ?

[guidav]

Oui, mais dans mon cas précis, bccb est à la fois un palindrome principal (les 4 dernières lettres) et un sous-palindrome de abccba. Faut-il le compter comme palindrome principal ou pas (on ne le compte pas comme sous palindrome, ok) ?

[Woodgate]

Question : dans "abccbaazertybccb", faut-il compter 2 palindromes (abccba et bccb) ou considère-ton que bccb est contenu dans abccba ?

On considère que bccb est compris dans abccba, et que donc ce n'est pas un palindrome. Seul abccba est consideré comme palindrome (car maximum).

[guidav]

Au global, c'est assez simple, je vais juste donner un algo car j'ai la flemme de coder :
On part de la première lettre $i=0 , on détermine la longueur $lmax qui reste dans la chaîne
Pour $l de $lmax à 2, on regarde si la sous-chaine de $i à $l est un palindrome.

Si oui, on le stocke dans un array (on vérifie s'il n'existe pas déjà) et on passe à la chaine suivante qui commence à $i+$l

Si non, on fait $i++ et on recommence.

Après, il faut voir comment tu veux gérer les morceaux de chaînes contenus dans 2 palindromes, du genre abcddcbaabce : il y a 2 palindromes, et la chaîne cba est présente dans les 2.
S'il faut les détecter, alors il faudra faire $i=$i+floor($l/2) (ou $i = $i+1, je ne suis pas certain) au lieu de $i=$i+$l, mais forcément ça sera plus long.

Corrigez-moi si je me trompe, évidemment.