#include<pthread.h>
#include<stdint.h>
#include<stdio.h>
#include<stdlib.h>
#include<stdarg.h>
#include<math.h>
#include <string.h>
#include <string.h>

struct node { int nb; struct node *t[6]; };
typedef struct node node;

node *r, *cr, *p;
int i, j, s, q, k, a_i, lim, mot[1000000], **ff, cff, **w, cw, cpt, *fpp, mat[10][100], len[10000], mmx, t;
char mode_in[100], mode_out[100], name[100];

int expo(int b, int e){
  int r = 1;
  for(;e--;) r *= b;
  return  r;
}

int eq(int *g, int *d, int l){
  for(; l--; ) if(g[l] != d[l]) return 0;
  return 1;
}

int square(int *m, int i, int l){
  for(; 2*l <= i; l++) if(eq(m+i-2*l, m+i-l, l)) return 1;
  return 0;
}//*/

void load_ff(){
  FILE *in = fopen("forbidden.txt", "r");
  char ch[3000];
  ff = (int**)malloc(10000*sizeof(int*));
  for(fgets(ch, 2000, in); strcmp(mode_out, ch); fgets(ch, 2000, in), ch[strlen(ch)-1] = 0);
  for(fgets(ch, 2000, in), cff = 0; strcmp(ch, "\n"); fgets(ch, 2000, in), cff++){
    ff[cff] = (int*)malloc((len[cff] = strlen(ch)-1)*sizeof(int));
    for(j = 0; j < len[cff]; j++) ff[cff][j] = ch[j]-'0';
  }
  fclose(in);
}

void load_w(){
  FILE *in = fopen(name, "r");
  char ch[3000];
  if(!in){printf("%s does not exist. Run this command to create it\n./pat %s 4 %d\n", name, mode_out, a_i*(mmx-1)); exit(0);}
  w = (int**)malloc(10000*sizeof(int*));
  for(fgets(ch, 2000, in), cw = 0; strcmp(ch, "\n"); fgets(ch, 2000, in), cw++){
    w[cw] = (int*)malloc((len[cw] = strlen(ch)-1)*sizeof(int));
    for(j = 0; j < len[cw]; j++) w[cw][j] = ch[j]-'0';
  }
  fclose(in);
}//*/

int** load_in(){
  FILE *in = fopen("morphisms.txt", "r");
  char ch[3000];
  int **tmp = (int**)malloc(10*sizeof(int*));
  for(fgets(ch, 2000, in); strcmp(mode_in, ch); fgets(ch, 2000, in), ch[strlen(ch)-1] = 0);
  for(fgets(ch, 2000, in), i = 0; strcmp(ch, "\n"); fgets(ch, 2000, in), i++){
    tmp[i] = (int*)malloc(strlen(ch)*sizeof(int));
    for(j = 0; ch[j]; j++) tmp[i][j] = ch[j]-'0';
    tmp[i][j] = -1;
  }
  fclose(in);
  return tmp;
}//*/

int* fp(int** mor, int l){
  int h[10];
  int *tmp = (int*)malloc(l*sizeof(int));
  for(*tmp = i = k = 0; k < l; i++) for(j = 0; (s = mor[tmp[i]][j]) >= 0 && k < l; j++) tmp[k++] = s;
  do{
    for(i = 0; i < a_i; h[i++] = 1);
    for(i = 0; h[tmp[i]] && i < a_i; h[tmp[i++]] = 0);
    if(i < a_i){ tmp++; lim--; }
  }while(i < a_i);
  return tmp;
}//*/

int ok(){
  if(square(mot, j, t)) return 0;
  for(q = 0; q < cff; q++) if(j >= len[q] && eq(ff[q], mot+j-len[q], len[q])) return 0;
  return 1;
}

void usage(){
  printf("Usage: map mode_in mode_out mmx\n");
  exit(0);
}

int main(int ac, char **av){
  if(ac != 4) usage();
  sprintf(mode_in, "%s", av[1]);
  sprintf(mode_out, "%s", av[2]);
  mmx  = atoi(av[3]);
  lim = 2000;
  if(!strcmp(mode_in, "f5")) a_i = 5;
  else if(!strcmp(mode_in, "f6")) a_i = 6;
  else if(!strcmp(mode_in, "f3")) a_i = 3;
  else usage();
  if(!strcmp(mode_out, "f5")) t = 1;//4n+1 n>=0
   else if(!strcmp(mode_out, "m1")) t = 1;//4n-2 n>=2
   else if(!strcmp(mode_out, "m2")) t = 1;//4n-2 n>=2
   else if(!strcmp(mode_out, "g8")) t = 7;//4n-6 n>=3
   else if(!strcmp(mode_out, "g12")) t = 9;//4n-6 n>=3
   else if(!strcmp(mode_out, "g14")) t = 9;//4n-1 n>=11
   else if(!strcmp(mode_out, "aabbcc")) t = 3;//4n+4 n>=6
  else if(!strcmp(mode_out, "f3")) t = 1;
   else if(!strcmp(mode_out, "g11")) t = 5;
   else if(!strcmp(mode_out, "g3")) t = 3;
   else if(!strcmp(mode_out, "aabbcabba")) t = 5;
  else usage();
  sprintf(name, "%s_pat_4_%d.txt", mode_out, a_i*(mmx-1));
  fpp = fp(load_in(), lim);
  load_w();
  load_ff();
  printf("mmx=%d a_i=%d mmx**a_i=%d\n", mmx, a_i, expo(mmx, a_i));
  for(; cw--;) for(cpt = expo(mmx, a_i); --cpt; ){
    k = cpt;
    for(i = j = 0; i < a_i; i++, k /= mmx){
      for(s = 0; s < k%mmx; s++) mat[fpp[i]][s] = w[cw][j++];
      mat[fpp[i]][s] = -1;
    }
    for(i = j = 0; j < lim && i < lim; i++) for(s = 0; mat[fpp[i]][s] >= 0 && i < lim; s++){
      mot[j++] = mat[fpp[i]][s];
      if(!ok()) i = lim;
    }
    if(i < lim){
      printf("yeah !!! cw=%d cpt=%d\n", cw, cpt);
      for(s = 0; s < a_i; s++){ if(mat[s][0] < 0) printf("e"); else for(k = 0; mat[s][k] >= 0; k++) printf("%d", mat[s][k]);printf("\n"); }
    }
  }
}