Discussion :

[roccocham]

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]

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]

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

[pseudocode]

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]

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]

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]

?

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

dons ton exemple il reste le meme abcdbcabbdca
.

[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 ??

[roccocham]

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"