le plus court prefixe

**roccocham** · 07/04/2010, 19h45

salut a tous:

je veux creer un algo qui calcule le plus court prefixe dans un mot c'est a dire si j'ai le mot ( abababab ) son plus court prefixe est ( ab ).

moi j'ai reussi a parcourir la chaine (le mot) par 2 pointeur mais le probleme c'est comment les stoker.

Voila mon algo:

Code C :

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
int i,j=0;
char v[N],w[N],*p,*q;
gets(v);  
p=v;
q=v+1;
for(i=0;i<strlen(v);i++)
{
    if (*p==*q)
    {
        w[j]=*p;
        p++;
        q++;
        j++;
    } 
    else
        q++; 
}
printf("w=%s\n",w);

**pseudocode** · 07/04/2010, 20h21

le plus court prefixe dans un mot c'est a dire si j'ai le mot ( abababab ) son plus court prefixe est ( ab )

?

Par exemple, c'est quoi le "plus court prefixe" dans (abcdbcabbdca) ?

**roccocham** · 07/04/2010, 20h33

voila la definition:
le plus court prefixe d'un mot w est : u tels que w=(u puissance k)

**roccocham** · 07/04/2010, 20h53

Envoyé par pseudocode

?

Par exemple, c'est quoi le "plus court prefixe" dans (abcdbcabbdca) ?

dons ton exemple il reste le meme abcdbcabbdca
.

**Shr3ck** · 07/04/2010, 21h31

Un préfixe c'est pas censé être genre : para, anti ??

Et juste pour voir si j'ai compris l'explication dans "coucou" le préfixe serait "cou" car "coucou" = "cou"². C'est ça ?

Et par curiosité, ça serait possible de connaitre le but de récupérer le préfixe d'un mot ??

**roccocham** · 07/04/2010, 21h40

Envoyé par Shr3ck

Un préfixe c'est pas censé être genre : para, anti ??

Et juste pour voir si j'ai compris l'explication dans "coucou" le préfixe serait "cou" car "coucou" = "cou"². C'est ça ?

Et par curiosité, ça serait possible de connaitre le but de récupérer le préfixe d'un mot ??

oui, c'est ça le sous mot qui se repete "cou"

**pseudocode** · 07/04/2010, 21h51

Envoyé par roccocham

voila la definition:
le plus court prefixe d'un mot w est : u tels que w=(u puissance k)

w = u puissance k = uuu...uuuu (k fois)

Si on fait un petit décalage circulaire, lettre par lettre, de (w) jusqu'a retrouver le mot de départ, alors on trouvera la valeur de u

(w) = abcabcabcabc

(w)<<1 = bcabcabcabca
(w)<<2 = cabcabcabcab
(w)<<3 = abcabcabcabc = (w)

donc (u) = 3 premieres lettres de (w) = (abc)
et k = longueur(w)/longueur(u) = 12/3 = 4

c'est à dire (w) = (abc) puissance 4

**roccocham** · 07/04/2010, 21h56

Envoyé par pseudocode

w = u puissance k = uuu...uuuu (k fois)

Si on fait un petit décalage circulaire, lettre par lettre, de (w) jusqu'a retrouver le mot de départ, alors on trouvera la valeur de u

(w) = abcabcabcabc

(w)<<1 = bcabcabcabca
(w)<<2 = cabcabcabcab
(w)<<3 = abcabcabcabc = (w)

donc (u) = 3 premieres lettres de (w) = (abc)
et k = longueur(w)/longueur(u) = 12/3 = 4

c'est à dire (w) = (abc) puissance 4

good alor u = abc

**pseudocode** · 07/04/2010, 22h30

Le plus proche du C que je peux faire en Java, c'est un truc comme ca:

Code java :

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
char[] w = "abcabcabcabc".toCharArray();
int wlen = w.length;
 
// pour chaque décalage possible
for(int shift=1;shift<=wlen;shift++) {
 
	// regarde si (w) = (w)<<shift 
	int i;
	for(i=0;i<wlen;i++)
		if (w[i]!=w[(i+shift)%wlen]) break;
 
	// si c'est le cas, affiche 'u' et sort de la boucle
	if (i==wlen) {
		String u = new String(w,0,shift);
		int k = wlen/shift;
		System.out.printf("w = (%s)^%d", u, k);
		break;
	}
}

**roccocham** · 07/04/2010, 22h54

Envoyé par pseudocode

Le plus proche du C que je peux faire en Java, c'est un truc comme ca:

Code java :

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
char[] w = "abcabcabcabc".toCharArray();
int wlen = w.length;
 
// pour chaque décalage possible
for(int shift=1;shift<=wlen;shift++) {
 
	// regarde si (w) = (w)<<shift 
	int i;
	for(i=0;i<wlen;i++)
		if (w[i]!=w[(i+shift)%wlen]) break;
 
	// si c'est le cas, affiche 'u' et sort de la boucle
	if (i==wlen) {
		String u = new String(w,0,shift);
		int k = wlen/shift;
		System.out.printf("w = (%s)^%d", u, k);
		break;
	}
}

mreci pseudocode mais je suis encore debuttant en c

votre fonction est difficile pour moi

voila mon nouveau algo si il ya une erreur merci de la corriger.

Code C :

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
#include<stdio.h>
#define N 50
 
main()
{ 
    int i,j=0,M=0;
 
    char v[N],w[N],*p,*q;
    for(i=0;i<N;i++)
    w[i]=NULL;
 
   gets(v);  
 
   p=v;
   q=v+1;
   for(i=0;i<strlen(v);i++)
   {if (*p==*q)
  { w[j]=*p;
   p++;
  q++;
  printf("w[%d]=%c\n",j,w[j]);
  j++;
 } 
  else
  q++; 
}
 printf("j=%d\n",j);
 M=strlen(v)-j;
  printf("M=%d\n",M);
 if(w[M-1]!=NULL)
 for(i=0;i<M;i++)
  printf("\n\nw[%d]=%c\n",i,w[i]);
  else
    printf("\n\nnooott okkk ");
 getch();
      }
 
}

**pseudocode** · 07/04/2010, 23h31

Envoyé par roccocham

voila mon nouveau algo si il ya une erreur merci de la corriger.

Je dirais que ca marche (*) si le mot de départ est effectivement une puissance (avec k>=2).

(*) mise a part un dépassement de buffer pour la variable 'q' dans la boucle for(). Je mettrais un while à la place :

for(i=0;i<strlen(v);i++) --> while (q<strlen(v))

**roccocham** · 07/04/2010, 23h55

Envoyé par pseudocode

Je dirais que ca marche (*) si le mot de départ est effectivement une puissance (avec k>=2).

(*) mise a part un dépassement de buffer pour la variable 'q' dans la boucle for(). Je mettrais un while à la place :

for(i=0;i<strlen(v);i++) --> while (q<strlen(v))

merciiiii pseudocode

**Zavonen** · 12/04/2010, 17h46

Curieux, en lisant rapidement les codes il me semble que personne n'utilise le fait que la longueur d'un préfixe doit être un diviseur de la longueur de la chaîne.

**pseudocode** · 12/04/2010, 17h56

Envoyé par Zavonen

Curieux, en lisant rapidement les codes il me semble que personne n'utilise le fait que la longueur d'un préfixe doit être un diviseur de la longueur de la chaîne.

Pas bête ça.

**josmiley** · 12/04/2010, 20h10

en python je ferai ça (je connais pas C désolé):

Code :

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

1
2
3
4
5
mot = 'coucou'
l = len(mot)
c=1
while mot.count(mot[:c])*c != l:c+=1
print mot[:c]

**Zavonen** · 12/04/2010, 23h07

Compte tenu de la remarque faite plus haut, et vu qu'il n'y a pas d'appel à 'count',ceci risque d'être plus efficace:

Code python :

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

1
2
3
4
5
6
7
 
mot = 'coucou'
l = len(mot)
for c in (i for i in xrange(1,l+1) if l%i==0):
    if mot==mot[:c]*(l/c) :
        print mot[:c]
        break

**josmiley** · 13/04/2010, 10h31

bien vu Zavonen ...
j'ajouterai donc ce code avec un if et un iter en moins:

Code python :

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

1
2
3
4
5
mot = 'coucou'
l = len(mot)
for c in range(1,l+1):
        if mot[:c]*(l/c)==mot:break
print mot[:c]

ou

Code python :

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

1
2
3
4
mot = 'coucou'
l,c = len(mot),1
while mot[:c]*(l/c)!=mot:c+=1
print mot[:c]

**Zavonen** · 13/04/2010, 14h00

@josmiley
Tu fais toujours le test pour tous les nombres entre 1 et l pas seulement pour les diviseurs de l et ton test coûte cher (plus cher qu'une division euclidienne si la chaîne est longue).

**josmiley** · 13/04/2010, 14h19

Envoyé par Zavonen

@josmiley
Tu fais toujours le test pour tous les nombres entre 1 et l pas seulement pour les diviseurs de l et ton test coûte cher (plus cher qu'une division euclidienne si la chaîne est longue).

oui, c'est vrai, si la chaine est longue ta méthode est bien meilleur.
c'est à adapter selon les besoins.

**solana** · 08/01/2011, 17h59

Bonjour

J'ai la même chose à faire mais dans le langage algorithmique.
Comme je ni connais rien en C pourrait tu stp décrire un peu ton algo les fonctions et à quoi correspondent les variables.

Merci

le plus court prefixe

Algorithmes et structures de données

Discussions similaires

Partager

Partager