Listing: GERMANA.CPP #include <stdio.h> #include <string.h> #include <stdlib.h> #include <alloc.h> #define NMAX 100 #define LMAX 255 #define KMAX 1000 int i,j,t,k,n,l,mj,ls; long *a,*aa,*tmp,min; int b[NMAX+1][NMAX+1]; char *p[KMAX+1]; int d[KMAX+1]; char *c[NMAX+1]; char buf[BUFSIZ]; FILE *f; void citeste(){ f=fopen("germana.in","rt"); fscanf(f,"%d %d %d",&n,&l,&k); for (i=1;i<=n;i++){ c[i]= new char[l+1]; if (!c[i]){ puts("Out of memory"); exit(1); } fscanf(f,"%s",c[i]); } fclose(f); } void build_b(){ char s[LMAX*2+1]; static int a[LMAX*2+10]; int ci,cj; for (ci=1;ci<=n;ci++) for (cj=1;cj<=n;cj++){ strcpy(s,c[ci]); if (ci!=cj) strcat(s,c[cj]); ls=strlen(s); a[0]=-1; a[1]=0; j=0; for (i=2;i<=ls;i++){ while (j>=0 && s[j]!=s[i-1]) j=a[j]; j++; a[i]=j; } b[ci][cj]=a[ls]; } } void rezolva(){ build_b(); aa=new long[n+1]; for (i=1;i<=n;i++) aa[i]=l; a=new long[n+1]; for (t=2;t<=k;t++){ if (!(p[t]=(char*) farmalloc(n+1))) { puts("Out of memory!"); exit(1); } for (i=1;i<=n;i++){ min=10000000; for (j=1;j<=n;j++) if (min>aa[j]+l-b[i][j]){ min=aa[j]+l-b[i][j]; mj=j; } a[i]=min; p[t][i]=mj; } tmp=a; a=aa; aa=tmp; } min=10000000; for (j=1;j<=n;j++) if (min>aa[j]){ min=aa[j]; mj=j; } } void scrie(){ printf("%ld\n",farcoreleft()); f=fopen("germana.out","wt"); fprintf(f,"%ld\n",min); for (i=k,j=mj;i>=1;i--){ d[i]=j; if (i>1) j=p[i][j]; } for (i=1;i<=k;i++) fprintf(f,"%s",c[d[i]]+b[d[i]][d[i-1]]); fclose(f); } void main(void){ citeste(); rezolva(); scrie(); } [cuprins] |