determiné la partie commune de deux chaines

Version imprimable

12/05/2009, 16h31
dxavier

determiné la partie commune de deux chaines
Bonjour,

Comment puis-je déterminer la partie commune de deux chemins différents ?
ex :
Code:

1 2 PATH1=/usr/local/bin PATH2=/usr/bin
Je voudrais récupérer /usr/ dans un script shell.

Merci de votre aide
12/05/2009, 17h02
kamouminator

c'est de l'algorithmique, je ne pense pas qu'il existe une fonction str*** qui le fasse,

principe: pour chaine1 et chaine2

deux boucle imbriquée:
tu recupere un premier char de chaine1, puis tu le compare a tous les char de chaine2, tant quils son differents
si tu a un match:
tu "sauvegarde" l'indice du char de la chaine2
tu passe au char suivant de chaine1 et tu le compare au char suivant celui qui a été matché sur chaine2 etc...

apres, je pense que dans ton cas il faudra matcher les "/" pour etre sur q'uil sagit bien d'un nom de dossier complet

Citation:

Envoyé par kamouminator

c'est de l'algorithmique, je ne pense pas qu'il existe une fonction str*** qui le fasse,

principe: pour chaine1 et chaine2

deux boucle imbriquée:
tu recupere un premier char de chaine1, puis tu le compare a tous les char de chaine2, tant quils son differents
si tu a un match:
tu "sauvegarde" l'indice du char de la chaine2
tu passe au char suivant de chaine1 et tu le compare au char suivant celui qui a été matché sur chaine2 etc...

apres, je pense que dans ton cas il faudra matcher les "/" pour etre sur q'uil sagit bien d'un nom de dossier complet

Un peu compliqué et surtout long (2 boucles imbriquées !!!). Il me semble que tu cherches une chaine 1 n'importe où dans la chaine 2 alors que le besoin initial ne mentionne qu'une correspondance dans la position (le plus long début commun aux 2 chaines) ce qui se résout en une seule boucle
Code:

1 2 3 4 5 6 Tant que 1er caractère chaine 1 = 1er caractère chaine 2 faire commun=commun + ledit premier caractère chaine1=chaine1 - son premier caractère chaine2=chaine2 - son premier caractère fin faire
Ca se fait avec du simple cut...
Code:

1 2 3 4 5 6 7 8 9 10 11 commun="" while true do c1=`echo $PATH1 |cut -c1` c2=`echo $PATH2 |cut -c1` test "$c1" != "$c2" && break commun="$commun$c1" PATH1=`echo $PATH1 |cut -c2-` PATH2=`echo $PATH2 |cut -c2-` done echo "$commun"

Citation:

Envoyé par Sve@r

Un peu compliqué et surtout long (2 boucles imbriquées !!!). Il me semble que tu cherches une chaine 1 n'importe où dans la chaine 2 alors que le besoin initial ne mentionne qu'une correspondance dans la position (le plus long début commun aux 2 chaines) ce qui se résout en une seule boucle

Exactement, la correspondance recherchée n'est qu'au début de la chaine.
Citation:
Envoyé par Sve@r
Code:

1 2 3 4 5 6 Tant que 1er caractère chaine 1 = 1er caractère chaine 2 faire commun=commun + ledit premier caractère chaine1=chaine1 - son premier caractère chaine2=chaine2 - son premier caractère fin faire
Ca se fait avec du simple cut...
Comme je ne maitrise pas entièrement le shell, je ne connaissais pas cut. Je pensais que je devais vérifier caractère pas caractère en incrémentant l'indice de la position. Mais ce que tu proposes fonctionne très bien, et est plus simple.

Merci

13/05/2009, 20h44
Sve@r

Citation:

Envoyé par dxavier

Comme je ne maitrise pas entièrement le shell, je ne connaissais pas cut.

En fait, cut est un programmme externe. Le shell est très limité dans ses possibilités de base mais il a la faculté de faire appel aux programmes externes quels qu'ils soient et récupérer ce que le programme affiche à l'écran (en le mettant entre backquottes `...`)

Et donc il existe un paquet de programmes, certains convertissent les caractères, certains trient les data, certains extraient des lignes correspondant au design que tu cherches etc. Tous ont en commun qu'ils affichent leur résultat à l'écran. Toi tout ce qui te reste à faire est d'utiliser dans ton shell le programme dont tu as besoin quand tu as besoin et récupérer son résultat via les backquottes.

Il fallait en plus tester si les deux chaines ne sont pas identiques.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
 
commun=""
if test "$PATH1" != "$PATH2"
then
	while true
	do
	c1=`echo $PATH1 |cut -c1`
	c2=`echo $PATH2 |cut -c1`
	test "$c1" != "$c2" && break
	commun="$commun$c1"
	PATH1=`echo $PATH1 |cut -c2-`
	PATH2=`echo $PATH2 |cut -c2-`
	done
else
	commun="$PATH1"
fi
echo "$commun"

Citation:
Envoyé par dxavier
Il fallait en plus tester si les deux chaines ne sont pas identiques.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 commun="" if test "$PATH1" != "$PATH2" then while true do c1=`echo $PATH1 |cut -c1` c2=`echo $PATH2 |cut -c1` test "$c1" != "$c2" && break commun="$commun$c1" PATH1=`echo $PATH1 |cut -c2-` PATH2=`echo $PATH2 |cut -c2-` done else commun="$PATH1" fi echo "$commun"
Effectivement, sans ça mon algo part en torche à la recherche d'une différence qu'il ne trouve pas (je HAIS les cas particuliers)

Petite optimisation: l'initialisation de la variable commun="" se fera dans le then car comme c'est écrit, si l'algo passe par le "else" elle est initialisée 2 fois dont une pour rien.

Après reflexion ça ne marche pas exactement comme je voudrais mais l'expression du besoin a été mal défini.
Comme les chaines sont des répertoires, je cherche la base commune du chemin, et pas forcément la chaine commune.
ex:

Code:

1
2
3
 
PATH1="/home/frederic"
PATH2="/home/francois"

Le bon résultat est "/home" et non "/home/fr". J'ai fait

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
 
nbslash_PATH1=`echo $PATH1 | tr -d "\n" | tr -s "/" "\n" | wc -l`
nbslash_PATH2=`echo $PATH2 | tr -d "\n" | tr -s "/" "\n" | wc -l`
while [ $nbslash_PATH1 -gt $nbslash_PATH2 ]
do
	PATH1=`echo "$PATH1" | sed "s/\(.*\)[\/\\].*/\1/"`
	nbslash_PATH1=$(($nbslash_PATH1-1))
done
while [ $nbslash_PATH1 -lt $nbslash_PATH2 ]
do
	PATH2=`echo "$PATH2" | sed "s/\(.*\)[\/\\].*/\1/"`
	nbslash_PATH2=$(($nbslash_PATH2-1))
done
while [[ "$PATH1" != "$PATH2" && $nbslash_PATH1 -gt 0 ]]
do
	nbslash_PATH1=$(($nbslash_PATH1-1))
	PATH1=`echo "$PATH1" | sed "s/\(.*\)[\/\\].*/\1/"`
	PATH2=`echo "$PATH2" | sed "s/\(.*\)[\/\\].*/\1/"`
done
 
echo $PATH1

Citation:
Envoyé par dxavier
Après reflexion ça ne marche pas exactement comme je voudrais mais l'expression du besoin a été mal défini.
Comme les chaines sont des répertoires, je cherche la base commune du chemin, et pas forcément la chaine commune.
ex:
Code:

1 2 3 PATH1="/home/frederic" PATH2="/home/francois"
Le bon résultat est "/home" et non "/home/fr". J'ai fait
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 nbslash_PATH1=`echo $PATH1 | tr -d "\n" | tr -s "/" "\n" | wc -l` nbslash_PATH2=`echo $PATH2 | tr -d "\n" | tr -s "/" "\n" | wc -l` while [ $nbslash_PATH1 -gt $nbslash_PATH2 ] do PATH1=`echo "$PATH1" | sed "s/$.*$[\/\\].*/\1/"` nbslash_PATH1=$(($nbslash_PATH1-1)) done while [ $nbslash_PATH1 -lt $nbslash_PATH2 ] do PATH2=`echo "$PATH2" | sed "s/$.*$[\/\\].*/\1/"` nbslash_PATH2=$(($nbslash_PATH2-1)) done while [[ "$PATH1" != "$PATH2" && $nbslash_PATH1 -gt 0 ]] do nbslash_PATH1=$(($nbslash_PATH1-1)) PATH1=`echo "$PATH1" | sed "s/$.*$[\/\\].*/\1/"` PATH2=`echo "$PATH2" | sed "s/$.*$[\/\\].*/\1/"` done echo $PATH1
Whaaaaa !!! Et vas-y que je te fais du tr et du sed à tire larigot et que je te mets pas de commentaire.
Petit test: reviens dans 6 mois et tente de te relire...

Une fois que t'as la chaîne commune, tu testes si c'est un répertoire sinon tu récupères le dirname (qui lui sera forcément un répertoire)
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 if test "$PATH1" != "$PATH2" then commun="" while true do c1=`echo $PATH1 |cut -c1` c2=`echo $PATH2 |cut -c1` test "$c1" != "$c2" && break commun="$commun$c1" PATH1=`echo $PATH1 |cut -c2-` PATH2=`echo $PATH2 |cut -c2-` done else commun="$PATH1" fi test ! -d "$commun" && commun=`dirname "$commun"` echo "$commun"