chaines cachees - Page 1

voila l'exo bonus qu'on avait a resoudre lors du test machine de ce matin, sur lequel j'ai bute.
meme a tete reposee, je ne trouve aucun algo pour resoudre l'exo:

Ecrire un programme qui prend en parametres deux chaines de
        caracteres et qui affiche la plus longue chaines de caracteres
        cachee dans les deux parametres.
        Si il y a plusieurs solutions, affichez n'importe laquelle.
        L'affichage sera suivi d'un '\n'.

        Soit s1 et s2 des chaines de caracteres.
        On dit que la chaine s1 est cachee dans la chaine s2 si on peut
        trouver chaque caractere de s1 dans s2 et ce dans le meme ordre que
        dans s1.
        Ainsi:
                "fgex.;" est cachee dans "tyf34gdgf;'ektufjhgdgex.;.;rtjynur6"
                "abc" est cachee dans "2altrb53c.sse"
                "abc"  n'est pas cachee dans "btarc"

        Si il n'y a pas deux parametres, le programme affiche '\n'.

exemple:
(login@host)./shide 'gegwqew}ewsgjyrju]iklrl9tl0' 'w@qe#}$e%^r&]*_r9-t0' | cat -e
wqe}er]r9t0$

des idees?

Houlà, c'est chaud !
Tot d'abord, je dirais de virer tous les caractères qui sont dans une chaîne mais pas dans l'autre, ça allège les chaînes et permet d'y voir plus clair.
Ensuite, une possibilité assez simple mais très basique et barbare (la seule qui me vient à l'esprit à froid) serait de construire toutes les chaînes cachées de 2 caractères ou plus dans la plus petite des 2 chaînes simplifiées.
Par exemple, dans 'btarc', on a :
* 2 caractères : bt ; ba ; br ; bc ; ta ; tr ; tc ; ar ; ac ; rc
* 3 caractères : bta ; btr ; btc ; bar ; bac ; brc ; tar ; tac ; trc ; arc
* 4 caractères : btar ; btac ; btrc ; barc ; tarc
* 5 caractères : btarc
Pour une chaîne de N caractères tous différents, il y a (2^N - N - 1) chaînes cachées différentes.
Et enfin, on teste la présence cachée éventuelle de ces sous-chaînes dans la plus grande chaîne simplifiée, en commençant par les plus longues sous-chaînes (que l'on peut d'ailleurs construire au fur et à mesure des tests pour gagner du temps).

Voilà voilà, pour répondre rapidement, c'est tout ce que je vois dans l'immédiat ...

@++

Je ferais un peu comme Ethaniel, tu vire les caractères inutile tu obtient une liste de caractères simplifié avec les bonne lettres. Tu regarde caractères par caractères dans l'autre la chaîne et tu reconstitue le mot, si lors de la boucle les 2 chaînes sont différentes alors il n'y a de chaine caché sinon tu affiche la liste.

Je crois que c'est assez classique, on l'a fait deux fois en prépa...

L'idée est de chercher les "chaînes cachées" (le terme qu'on emploie est "sous-suite commune" je crois) parmi les i premiers caractères de s1 et les j premiers caractères de s2. La meilleure chaîne cachée s'appelle m[i,j], à partir de là tu déduis facilement la relation, pour i et j >= 1 :
m[i,j] = max(m[i-1,j],m[i,j-1]) union { c / s1[i]=s2[j]=c }
où max désigne "la" plus longue des deux chaînes (oui, je sais, c pas une relation d'ordre).

Si tu veux faire un algorithme efficace, tu peux même ne calculer que les longueurs dans un premier temps, puis "remonter" dans la matrice pour retrouver ta chaîne (tu peux même trouver l'ensemble des chaînes )

Ceci devrait marcher (pas testé!):

char *hidden(char *p, char *q) {
 char *m=calloc(1,1);
 for(char *p1=p;*p1;p1++) {
  char *q1=q;
  l1:
  q1=strchr(q1,*p1);
  if (!q1) continue;
  char *h=hidden(p1+1,q1+1);
  if (strlen(h)+1>strlen(m)) {
   h=realloc(h,strlen(h)+2);
   memmove(h+1,h,strlen(h)+1);
   *h=*p1;
   free(m);
   m=h;
  } else free(h);
  q1++;
  goto l1;
 }
 return m;
}

EDIT: Il faudrait peut-être utiliser la valeur retournée par realloc, rien ne dit qu'elle n'a pas changé. J'ai donc rajouté h=. Strictement parlant, il faudrait aussi tester à chaque allocation si on n'a pas NULL, mais je poste ici un algorithme, pas un programme tout fait.

EDIT 2: Oups... Le séparateur entre 2 arguments d'une fonction est évidemment ',', pas ';'.

Ton algo est en O(n) en mémoire, mais en O(n^3) en temps (prendre p=q="0000...0"). Le mien est en O(n^2) en mémoire, mais en O(n^2) aussi en temps
A part ça j'ai pas vu de bug non plus

[titillage=medium-low]
Au fait, si je veux jouer sur les mots, ton post ./43 (et le ./44 qui suit) me fait penser que ton algo est en fait en O(n^4) ^^
[/titillage]

[titillage=high]
Et si je veux me la jouer chieur, je dirai que l'implémentation du mien se fait "naturellement" en O(n^2) puisqu'on a toutes les données qu'il faut dès le départ et on connaît la taille de ce qu'il faut allouer.

(et c'est mon algorithme qu'est le meilleur, d'abord )
[/titillage]

Le memmove est aussi en O(n), donc la présence ou non du realloc ne change rien ici.

Et ça ne te viendrait jamais à l'esprit de stocker ta chaîne à l'envers?

Et d'ailleurs si ça peut te rassurer il y a même un container STL (deque) qui gère les tableaux qui grandissent dans les deux sens, avec insertions et lookups en O(1) (remarque, ici, une liste chaînée suffirait, mais vive le gaspillage de mem )

Pollux :
(et c'est mon algorithme qu'est le meilleur, d'abord )

La mienne est plus grosse ©

En effet, sa routine est nettement plus grosse que la mienne à mon avis. Ce n'est pas vraiment une bonne chose.

char *hidden(char *p,char *q) {
  int n=strlen(p),m=strlen(q),z;
  void *t=calloc(n+1,m+1);
  for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
      t[m*i+j] = max(t[m*(i-1)+j],t[m*i+j-1]) + (p[i-1]==q[j-1]);
  char *r=malloc(z=t[m*n-1]+1);
  r[--z]=0;
  for (int i=n-1,j=m-1; i>=0 && j>=0; t[m*i+j-1]>t[m*(i-1)+j] ? j-- : i--)
    if (p[i]==q[j]) r[--z]=p[i];
  free(t);
  return r;
}

Tu trouves ça plus gros? Et pour un algo en O(n^2) au lieu de O(n^4), je trouve que ça vaut le coup

[EDIT : inversé deux trucs dans la dernière boucle 'for' pour plus de cohérence]

En tout cas c'est bien laid, tu devrais mettre des espaces autours de tous tes operateurs

Kevin > Franchement... On s'en tape de la place, SURTOUT si c'est pour passer de O(n^4) à O(n^2). Je sais pas trop ou t'apprends l'info mais chez moi on se ferait fusiller sur place à expliquer que l'algo en O(n^4) est meilleur parcequ'il prend 3 octets et demi de moins

En tout cas c'est bien laid, tu devrais mettre des espaces autours de tous tes operateurs

J'aime bien programmer sans trop d'espaces, et comme je suis habitué ben ça me dérange pas. Bon cela dit j'ai écrit ça pour que ça soit le plus compact possible, hein Par exemple si j'avais voulu faire un truc propre (i.e. sans risque de bug qui apparaîtrait à la première modification), j'aurais écrit "int z=t[m*n-1]" avant la déclaration de r...

D'ailleurs je trouve que si quelqu'un devait mettre des espaces, ce serait l'IDE, avec une sensibilité paramétrable et un nombre "fractionnaire" et non entier d'espaces (et puis ça éviterait les bêtises du type "3 + x>>1"). Un jour^(TM), je ferai une vraie IDE sur PC qui travaille sur une représentation en XML et pas sur du texte brut (mais c'est long ).

Mais c'est très dommage que la priorité de >> soit plus petite que celle de +, je trouve. Il serait plus cohérent selon moi que ce soi l'inverse.

Il y a beaucoup de choses très dommages en C (notamment les priorités...)

Sasume> Oui, bien sûr (d'ailleurs on en avait déjà parlé y a qqs mois). Cela dit ils ont utilisé ce défaut à bon escient pour le C++ (mystream << x+1)

Pollux :

char *hidden(char *p,char *q) {
  int n=strlen(p),m=strlen(q),z;
  void *t=calloc(n+1,m+1);
  for (int i=1;i<=n;i++)
    for (int j=1;j<=m;j++)
      t[m*i+j] = max(t[m*(i-1)+j],t[m*i+j-1]) + (p[i-1]==q[j-1]);
  char *r=malloc(z=t[m*n-1]+1);
  r[--z]=0;
  for (int i=n-1,j=m-1; i>=0 && j>=0; t[m*i+j-1]>t[m*(i-1)+j] ? j-- : i--)
    if (p[i]==q[j]) r[--z]=p[i];
  free(t);
  return r;
}

Tu trouves ça plus gros?

Ton code, apparemment pour le faire paraître plus petit, est largement illisible. Et ce ne sont pas les espaces autour des opérateurs qui vont y changer quelque chose.

Vertyos :
Kevin > Franchement... On s'en tape de la place, SURTOUT si c'est pour passer de O(n^4) à O(n^2). Je sais pas trop ou t'apprends l'info mais chez moi on se ferait fusiller sur place à expliquer que l'algo en O(n^4) est meilleur parcequ'il prend 3 octets et demi de moins

Chez nous aussi, je pense.
Mais: Chez nous, dans tous les cours à part l'algorithmie, ils préféreraient ma routine lisible en O(n⁴) à celle de Pollux en O(n²), mais avec des horreurs style la boucle presque entière codée dans l'instruction for. Cela dit, si quelqu'un pond une implémentation lisible et bien commentée de l'algorithme de Pollux, je suppose qu'ils sont contents.

Pollux, ta routine est fausse. Il faut remplacer void *t par char *t. (Mais bon, la mienne l'était aussi. J'ai déjà corrigé mon erreur. )

J'ai mesuré. En ne comptant pas les fonctions de TIGCCLIB (qui sont des fonctions d'allocation mémoire standard et seront de toute façon nécessaires à un endroit où un autre pour un vrai programme), mais juste le code lui-même, sous TIGCC, ma routine fait 224 octets, la tienne fait 258 octets. Mais bon, la grosse fonction realloc gâche tout. En codant spécifiquement pour calculatrice, j'utiliserais plutôt les handles.

On va voir ce que ça donne avec GTC

Visiblement TIGCC triche et favorise ta routine

J'ai désactivé le plus de stub possible : compatible avec toutes les calc, NO_EXIT_SUPPORT, MIN_AMS=100.
Voilà ce que ça donne :

                 GTC      GCC 3.3.1
routine Kevin    415      489
routine Pollux   409      625

Il semblerait donc que mon algo soit plus petit, malgré la mauvaise volonté évidente de TIGCC

Ton code, apparemment pour le faire paraître plus petit, est largement illisible. Et ce ne sont pas les espaces autour des opérateurs qui vont y changer quelque chose.

Il est parfaitement lisible, il manque peut-être de commentaires mais à part ça il est pas si horrible que ça

des horreurs style la boucle presque entière codée dans l'instruction for

Absolument pas. Les 2 premières boucles for sont on ne peut plus classiques, et la dernière est parfaitement logique : il s'agit, comme pour n'importe quelle boucle for, de choisir le critère d'évolution de la variable. Ici, il se trouve que la variable est le couple (i,j), donc au lieu de faire :
for (int i=n-1; i>=0; i--)
ou
for (int j=m-1; j>=0; j--)
on est obligé de rajouter un ?: pour savoir quelle variable on veut décrémenter, à savoir :
for (int i=n-1,j=m-1; i>=0 && j>=0; condition ? i-- : j--)

Pour moi ça n'a rien de tordu, même si ce n'est pas la boucle for "académique".

Je ne sais pas comment tu as mesuré, parce que chez moi, la taille de l'exécutable est plus grosse avec ma routine à cause de la grosse routine realloc. (Cf. ./21: "Mais bon, la grosse fonction realloc gâche tout. ".) Les chiffres que j'ai postés sont ceux de la routine seule, sans les routines de TIGCCLIB.

Je parle du programme complet, avec un _main vide. Mais alors si l'exécutable est plus gros avec ta routine, j'ai du mal à comprendre la taille de ma routine sous TIGCC

Moi, pour le programme entier avec tout linké, et avec MIN_AMS=100, j'ai 367 octets (taille on-calc) pour ma routine et 317 octets (taille on-calc) pour la tienne. Comme déjà dit, c'est realloc qui est lourd sous TIGCC.

Bizarre... Il me semble bien avoir pris la dernière version sur tigcc.ticalc.org pourtant... Peut-être la détection du type de calc? (j'ai pas mis (_)NO_CALC_DETECT) Mais je comprends pas pkoi ma routine est aussi gigantesque sous TIGCC Bon, je réessaierai.

Moi, j'ai compilé pour les 3 modèles tout simplement. Il n'y a rien qui dépend du modèle ici.
Et soit tu ne sais pas utiliser GTools Compiler non plus (), soit il est moins efficace ( aussi).

erf en attendant comme je sais pas utiliser TIGCC non plus, GTC reste plus efficace

Ben non, pour l'instant, TIGCC en est à 48 octets de moins pour ma routine et 96 de moins pour la tienne. J'attends toujours des résultats meilleurs de ta part.