Attenzione alla
gets
Se leggi con attenzione vedrai che gets scandisce l'input e si ferma SOLO dopo aver trovato un \n. Il problema nasce dal fatto che lui non si ferma quando è finito lo spazio per contenere la stringa. Siccome la tua stringa può contenere NMAX - 1 caratteri (l'ultimo carattere è riservato per il fine stringa ovvero il \0) e la stringa di input è maggiore di questo valore, vai in buffer overflow.
La soluzione sarebbe quella di usare
fgets che come parametro ha anche il numero di caratteri da leggere dal file (in questo caso l'input stdin).
Quindi la modifica da fare sarà del tipo:
fgets(parola,NMAX-1,stdin)
Infine siccome fgets aggiunge anche il \n nel buffer dovresti rimuoverlo.
s = strlen(parola);
if(parola[s-1] == '\n')
{
parola[s-1] = '\0';
s--;
}