2 грамма Цепь Маркова

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int len;
typedef struct {
  unsigned key;
  char *val[3];
  unsigned char num;
} Chain;
 
unsigned fnv_32a(char *s, char *e) {
  unsigned hash = 0; // 0x811C9DC5, 0xEDB88320
  if (*s == 32) s++;
  while (s < e) {
    // fprintf(stderr, ":%u", *s);
    hash ^= *s++;
    hash *= 0x01000193;
  }
  return hash;
}
 
int exist_key(unsigned key, int len, Chain *chain) {
  for (int i = 0; i < len; i++) if (chain[i].key == key) return i;
  return -1;
}
 
Chain *make_chain(char *t, char *t2, int d, int *len) {
  char *e = t;
  unsigned char ptr[100] = {0}, words = 1; // count of words
  while (*e++) if (*e == ' ') ptr[words++] = e - t;
  ptr[words] = e - t - 1;
  *len = words - d; // lenght of chain
  Chain *chain = (Chain *)calloc(*len, sizeof(Chain));
 
  for (int x = 0, i = 0, j = d; i < *len; i++, j++) {
    unsigned key = fnv_32a(t + ptr[i], t + ptr[j]); // n-gram text as key
    int id = exist_key(key, *len, chain);
    *(t2 + ptr[j + 1]) = 0; // end of key value. next word after key is value
 
    if (id != -1) { // if key exist
      int val_id = 1;
      while (chain[id].val[val_id] != NULL)
        val_id++;
      chain[id].val[val_id] = t2 + ptr[j] + 1; // value of key
      // fprintf(stderr, " +%d %s\n", id, chain[id].val[val_id]);
      chain[id].num = ++val_id;
      continue;
    }
    chain[x].key = key;
    chain[x].num = 1;
    chain[x++].val[0] = t2 + ptr[j] + 1; // value of key
    // fprintf(stderr, " %s\n", chain[x - 1].val[0]);
  }
  return chain;
}
 
int pick_option_index(int num) {
  static unsigned random_seed = 0;
  random_seed += 7;
  return random_seed % num;
}
 
void get_chain(char *t, int d, int len, Chain *chain) {
  static char *e = NULL; // to increase speed of adding words from chain
  if (e == NULL) e = t;
  static unsigned char ptr[100] = {0}, words = 1; // count of words
  while (*e++) if (*e == ' ') ptr[words++] = e - t;
  ptr[words] = e - t - 1;
  // for (int i = 0; i <= words; i++) fprintf(stderr, "%u \n", ptr[i]);
  unsigned key = fnv_32a(t + ptr[words - d], t + ptr[words]); // n-gram text as key
  int id = exist_key(key, len, chain);
  if (id >= 0) {
    strcat(t, " ");
    int val_id = pick_option_index(chain[id].num);
    strcat(t, chain[id].val[val_id]);
    words++;
  }
}
 
int need_add(char *e, int l) {
  unsigned char words = 1; // count of words
  while (*e++) if (*e == ' ') words++;
  return l - words; // is need to add words
}
 
int main() {
  char t[1001]; // array of key
  scanf("%[^\n]", t);
  char t2[strlen(t) + 1]; // array of value
  strcpy(t2, t);
  int d; // n-gram
  scanf("%d", &d);
  int len; // lenght of chain
  Chain *chain = make_chain(t, t2, d, &len);
 
  int l; // length of outputed words
  scanf("%d", &l);
  fgetc(stdin);
  char s[1001]; // initial string
  scanf("%[^\n]", s);
  int add = need_add(s, l); // words
  for (int i = 0; i < add; i++) {
    get_chain(s, d, len, chain); // adding words
    // fprintf(stderr, "\n%s \n", s);
  }
 
  printf("%s\n", s);
  free(chain);
  return 0;
}