#include<stdio.h>
#include<stdlib.h>
#include<string.h>
enum {
NPREF = 2, /* number of prefix words */
NHASH = 4093, /* size of state hash table array */
MAXGEN = 10000, /* maxmun words generated */
MULTIPLIER = 31,
};
typedef struct State State;
typedef struct Suffix Suffix;
struct State { /* prefix + suffix list */
char *pref[NPREF]; /* prefix words */
Suffix *suf; /* list of suffixes */
State *next; /* next in list of suffix */
};
struct Suffix { /* list of suffixes */
char *word; /* suffixes */
Suffix *next; /* next in list of suffixes */
};
State *statetab[NHASH]; /* hash tabke of states */
char NONWORD[] = "\n"; /* cannot appear as real word */
unsigned int hash(char *s[NPREF]);
State* lookup(char *prefix[NPREF], int create);
void build(char *prefix[NPREF], FILE *f);
void add(char *prefix[NPREF], char *suffix);
void addsuffix(State *sp, char *suffix);
void generate(int nwords);
int main()
{
int i, nwords = MAXGEN;
char *prefix[NPREF]; /* current input prefix */
for(i = 0; i < NPREF; i++) /* set up inittial prefix */
prefix[i] = NONWORD;
build(prefix, stdin);
add(prefix, NONWORD);
generate(nwords);
return 0;
}
/* hash: compute hash value for array of NPREF string */
unsigned int hash(char *s[NPREF])
{
unsigned int h;
unsigned char *p;
int i;
h = 0;
for(i = 0; i < NPREF; i++)
for(p = (unsigned char *) s[i]; *p != '\0'; p++)
h = MULTIPLIER * h + *p;
return h % NHASH;
}
/* lookup: search for prefix; create if requested. */
/* returns pointer if present or created; NULL if not */
/* creation dosen't strdup so strings mustn't change later. */
State* lookup(char *prefix[NPREF], int create)
{
int i, h;
State *sp;
h = hash(prefix);
for(sp = statetab[h]; sp != NULL; sp = sp->next)
{
for(i = 0; i < NPREF; i++)
if(strcmp(prefix[i], sp->pref[i]) != 0)
break;
if(i == NPREF) /* found it */
return sp;
}
if(create)
{
sp = (State *) malloc(sizeof(State));
if(sp == NULL)
return NULL;
for(i = 0; i < NPREF; i++)
sp->pref[i] = prefix[i];
sp->suf = NULL;
sp->next = statetab[h];
statetab[h] = sp;
}
return sp;
}
/* bulid: read input,build prefix table */
void build(char *prefix[NPREF], FILE *f)
{
char buf[100], fmt[10];
/* create a format string; %s could overflow buf */
sprintf(fmt, "%%%ds",sizeof(buf)-1);
while(fscanf(f, fmt, buf) != EOF)
add(prefix, buf);
}
/* add: add word to suffix list, update prefix */
void add(char *prefix[NPREF], char *suffix)
{
State *sp;
sp = lookup(prefix, 1); /* create if not found */
addsuffix(sp, suffix);
/* move the words down the prefix */
memmove(prefix, prefix + 1, (NPREF-1) * sizeof(prefix[0]));
prefix[NPREF-1] = suffix;
}
/* addsuffix: add to state. suffix must not change later */
void addsuffix(State *sp, char *suffix)
{
Suffix *suf;
suf = (Suffix *) malloc(sizeof(Suffix));
if(suf == NULL)
return ;
suf->word = suffix;
suf->next = sp->suf;
sp->suf = suf;
}
/* generate: produce output, one word per line */
void generate(int nwords)
{
State *sp;
Suffix *suf;
char *prefix[NPREF], *w;
int i, nmatch;
for(i = 0; i < NPREF; i++) /* reset initial prefix */
prefix[i] = NONWORD;
for(i = 0; i < nwords; i++)
{
sp = lookup(prefix, 0);
nmatch = 0;
for(suf = sp->suf; suf != NULL; suf = suf->next)
if(rand() % ++nmatch == 0) /* prob = 1/nmatch */
w = suf->word;
if(strcmp(w, NONWORD) == 0)
break;
printf("%s\n", w);
memmove(prefix, prefix + 1, (NPREF-1) * sizeof(prefix[0]));
prefix[NPREF-1] = w;
}
}
