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

void alokuj_pamet(char **p, const int bytu)
{
  if ((*p = (char *) calloc(bytu, 1 /* sizeof(char) */)) == NULL) { /* sizeof(char) is defined to be 1 - http://en.wikipedia.org/wiki/Sizeof */
  /* if ((*p = (char *) malloc(bytu)) == NULL) { */
    printf("Malo pameti!\n");
    exit(1);
  }
  else {
    /* **p = '\0';  Pri pouziti malloc je nutno vynulovat zacatek, protoze se do retezce pridava. */
    #ifdef DEBUG
      printf("%p %d bytu\n", *p, bytu);
    #endif
  }
}

void uvolni_pamet(void **p)
{
  free((void *) *p);
  #ifdef DEBUG
    printf("%p uvolneno.\n", *p);
  #endif
  *p = NULL;
}

int pocet_podretezcu(const char *where, const char *what)
{
  int i = 0;
  char *pozice;
  while ((pozice = strstr(where, what)) != NULL) { /* V promenne pozice bude adresa prvniho znaku retezce what v retezci where. */
    i++;
    where = pozice + strlen(what); /* Uber z retezce zpracovany zacatek. */
  }
  return i;
}

void replace_recursively(const char *st, char *vysledek, const char *orig, const char *repl)
{ /* http://www.roseindia.net/c-tutorials/c-replace-string.shtml */
  char *pozice;
  if (!(pozice = strstr(st, orig))) {
    strcat(vysledek, st); /* Pridej zbytek retezce. */
  }
  else {
    strncat(vysledek, st, pozice - st); /* Zkopiruj vse pred nahrazovanym retezcem. */
    strcat(vysledek, repl); /* Pridej nahrazujici retezec. */
    st = pozice + strlen(orig); /* Uber z puvodniho retezce zpracovany zacatek. */
    replace_recursively(st, vysledek, orig, repl);
  }
}

void replace(const char *st, char *vysledek, const char *orig, const char *repl)
{
  char *pozice;
  while ((pozice = strstr(st, orig)) != NULL) {
    strncat(vysledek, st, pozice - st); /* Zkopiruj vse pred nahrazovanym retezcem. */
    strcat(vysledek, repl); /* Pridej nahrazujici retezec. */
    st = pozice + strlen(orig); /* Uber z puvodniho retezce zpracovany zacatek. */
  }
  strcat(vysledek, st); /* Pridej zbytek retezce. */
}

int main(void) {
  char *retezec = "Hello world!";
  char *podretezec = "world";
  char *nahrazujici_podretezec = "India";
  char *vysledny_retezec_rekurzivne = NULL, *vysledny_retezec = NULL;
  int delka_vysledneho_retezce = strlen(retezec) + pocet_podretezcu(retezec, podretezec) * (strlen(nahrazujici_podretezec) - strlen(podretezec));
  alokuj_pamet(&vysledny_retezec_rekurzivne, delka_vysledneho_retezce + 1);
  replace_recursively(retezec, vysledny_retezec_rekurzivne, podretezec, nahrazujici_podretezec);
  puts(vysledny_retezec_rekurzivne);
  uvolni_pamet((void **) &vysledny_retezec_rekurzivne);
  alokuj_pamet(&vysledny_retezec, delka_vysledneho_retezce + 1); /* Musime alokovat o jeden bajt vice pro ukoncujici znak '\0'. */
  replace(retezec, vysledny_retezec, podretezec, nahrazujici_podretezec);
  puts(vysledny_retezec);
  uvolni_pamet((void **) &vysledny_retezec);
  return 0;
}