le plus court prefixe

Version imprimable

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:

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

07/04/2010, 20h21
pseudocode

Citation:

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

:koi: ?

Par exemple, c'est quoi le "plus court prefixe" dans (abcdbcabbdca) ?
07/04/2010, 20h33
roccocham

voila la definition:
le plus court prefixe d'un mot w est : u tels que w=(u puissance k)
07/04/2010, 20h53
roccocham

Citation:

Envoyé par pseudocode

:koi: ?

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

dons ton exemple il reste le meme abcdbcabbdca
.
07/04/2010, 21h31
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 ??
07/04/2010, 21h40
roccocham

Citation:

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"
07/04/2010, 21h51
pseudocode

Citation:

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
07/04/2010, 21h56
roccocham

Citation:

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

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

Code:

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;
	}
}

Citation:

Envoyé par pseudocode

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

Code:

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 :lol: votre fonction est difficile pour moi :cry: voila mon nouveau algo si il ya une erreur merci de la corriger.

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
#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();
      }
 
}

07/04/2010, 23h31
pseudocode

Citation:

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))
07/04/2010, 23h55
roccocham

Citation:

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:ccool:
12/04/2010, 17h46
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.
12/04/2010, 17h56
pseudocode

Citation:

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. :aie:

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

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

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:

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

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

Code:

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]

Code:

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

13/04/2010, 14h00
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).
13/04/2010, 14h19
josmiley

Citation:

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.
08/01/2011, 17h59
solana

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