#include <stdio.h>
#include <stdlib.h>
#include <string.h>


struct vals {
	char **values;
	int elt;
};


struct vals *merge_vals(struct vals *v1, struct vals *v2){
	int i,idx=0;
	struct vals *result=NULL;

	
	result = (struct vals *)malloc(sizeof(struct vals));
	result->elt = 0;
	if(v1) result->elt += v1->elt;
	if(v2) result->elt += v2->elt;
		

	result->values = (char **) malloc(sizeof(char *) * result->elt);
	if(v1)
		for(i=0;i<v1->elt;i++)
			result->values[idx++] = v1->values[i];
	if(v2)
		for(i=0;i<v2->elt;i++) 
			result->values[idx++] = v2->values[i];
	
	fprintf(stderr,"DEBUG: merged v1 (%i elt) with v2 (%i elt) => result (%i elt)\n",
			v1 ? v1->elt : 0, v2 ? v2->elt : 0,--idx);
	
	return(result);
}


/*
 * Generate all possible values for given "base" string using "space" chars at given offset.
 * Exemple:
 *
 * base   = aaaXaa
 * space  = abc
 * offset = 3 (begins at 0)
 * 
 * result = { "aaaaaa", "aaabaa", "aaacaa" }
 */
struct vals* gen_one_digit(char *base, char *space, int offset){
	int i;
	/* rlen is length of char **result, blen is len of space (a-zA-Z0-9) */
	int rlen, blen;
	struct vals *final  = NULL;
	struct vals *result = NULL;

	rlen = strlen(space);
	blen = strlen(base);


	result = (struct vals *) malloc(sizeof(struct vals));
	result->elt  = rlen;
	result->values = (char **)malloc(sizeof(char *) * rlen);

	final = (struct vals *) malloc(sizeof(struct vals));
	final->elt  = 0;
	final->values = NULL;



	for(i=0; i < rlen; i++){
		result->values[i] = (char *) strdup(base);
		result->values[i][offset] = space[i];

		if(offset < (blen - 1))
		{
			final = merge_vals(final,gen_one_digit(result->values[i],space,offset+1));
		}
	}
	fprintf(stderr,"DEBUG: %s %s %i => result(%p) final(%p)\n",base,space,offset,result,final);
	return (offset == blen - 1 ? result : final);
}
			

int main(int ac, char **av){
	struct vals *final;
	char *space, *base= NULL;
	int len;
	
	if(ac != 3){
		fprintf(stderr,"Usage: %s <possible characters> <len>\n",av[0]);
		exit(255);
	}
	space = av[1];
	len = atoi(av[2]);

	base = malloc(sizeof(char) * (len + 1));
	memset(base,'X',len);
	base[len] = '\0';
	
	final = gen_one_digit(base, space, 0);
	
	if(!final){
		fprintf(stderr,"Error !\n");
		exit(EXIT_FAILURE);
	}

	fprintf(stderr,"Final: %i elements\n",final->elt);

	for(len=0; len < final->elt; len++){
		printf("%s\n",final->values[len]);
	}

	exit(EXIT_SUCCESS);
}