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]