/Copyright (C)2000 Lucent Technologies * /Modified from markov.c in 'Programming Pearls'by Jon Bentley * /markovlet.c--generate letter-level random text from input text Alg:Store text in an array on input Scan complete text for each output character (Randomly select one matching k-gram) */ #include <stdio.h> #include <stdlib.h> char x[5000000]; int main() int c,i,eqsofar,max,n 0,k =5; char *p,*nextp,*qi while ((c getchar())!=EOF) x[n++]=c: x[n]=0; p xi srand(1); for (max =2000;max >0;max--){ egsofar 0; for (q x;q x n-k 1;q++){ for(i=0;i<k&&*(p+i)==*(q+i);i++) if (i==k) if (rand()+teqsofar ==0) nextp =q; } c =*(nextp+k); if(c==0) break; putchar(c); p nextp+1; } return 0;
/* Copyright (C) 2000 Lucent Technologies */ /* Modified from markov.c in 'Programming Pearls' by Jon Bentley */ /* markovlet.c -- generate letter-level random text from input text Alg: Store text in an array on input Scan complete text for each output character (Randomly select one matching k-gram) */ #include <stdio.h> #include <stdlib.h> char x[5000000]; int main() { int c, i, eqsofar, max, n = 0, k = 5; char *p, *nextp, *q; while ((c = getchar()) != EOF) x[n++] = c; x[n] = 0; p = x; srand(1); for (max = 2000; max > 0; max--) { eqsofar = 0; for (q = x; q < x + n - k + 1; q++) { for (i = 0; i < k && *(p+i) == *(q+i); i++) ; if (i == k) if (rand() % ++eqsofar == 0) nextp = q; } c = *(nextp+k); if (c == 0) break; putchar(c); p = nextp+1; } return 0; }
/Copyright (C)1999 Lucent Technologies * /From 'Programming Pearls'by Jon Bentley * /markov.c--generate random text from input document * #include <stdio.h> #include <stdlib.h> #include <string.h> char inputchars[4300000]; char *word[800000]; int nword 0; int k 2; int wordncmp(char *p,char*q) { int n k; for（;*p==*g:p++,q+) if(*p=0&&--n==0) return 0; return *p -*qi int sortcmp(char **p,char **q) return wordncmp(*p,*q); 八 char *skip(char *p,int n) { for(;n>0;p++) if(*p==0) n--; return p; int main() int i,wordsleft =10000,1,m,u; char *phrase,*p; word [0]inputchars; while(scanf("号s",word[nword])！=EoF){ word[nword+1]word[nword]strlen(word[nword])+1; nword++; for(=0;i<k;i++) word[nword][i]=0; for (i=0;i<k;i++) printf("&s\n",word[i]); gsort(word,nword,sizeof(word[0]),sortcmp); phrase inputchars; for (wordsleft 0;wordsleft--){ 1=-1； u nword; whi1e(1+1!=u){ m=(1+u)/2; if (wordncmp(word[m],phrase)<0) 1=m else u=m; } for (i =0;wordncmp(phrase,word[uti])==0;i++) if(rand()号(i+1)==0) p word[u+i]; phrase skip(p,1); if (strlen(skip(phrase,k-1))==0)
/* Copyright (C) 1999 Lucent Technologies */ /* From 'Programming Pearls' by Jon Bentley */ /* markov.c -- generate random text from input document */ #include <stdio.h> #include <stdlib.h> #include <string.h> char inputchars[4300000]; char *word[800000]; int nword = 0; int k = 2; int wordncmp(char *p, char* q) { int n = k; for ( ; *p == *q; p++, q++) if (*p == 0 && --n == 0) return 0; return *p - *q; } int sortcmp(char **p, char **q) { return wordncmp(*p, *q); } char *skip(char *p, int n) { for ( ; n > 0; p++) if (*p == 0) n--; return p; } int main() { int i, wordsleft = 10000, l, m, u; char *phrase, *p; word[0] = inputchars; while (scanf("%s", word[nword]) != EOF) { word[nword+1] = word[nword] + strlen(word[nword]) + 1; nword++; } for (i = 0; i < k; i++) word[nword][i] = 0; for (i = 0; i < k; i++) printf("%s\n", word[i]); qsort(word, nword, sizeof(word[0]), sortcmp); phrase = inputchars; for ( ; wordsleft > 0; wordsleft--) { l = -1; u = nword; while (l+1 != u) { m = (l + u) / 2; if (wordncmp(word[m], phrase) < 0) l = m; else u = m; } for (i = 0; wordncmp(phrase, word[u+i]) == 0; i++) if (rand() % (i+1) == 0) p = word[u+i]; phrase = skip(p, 1); if (strlen(skip(phrase, k-1)) == 0)
break; printf("s\n",skip(phrase,k-1)); } return 0;
break; printf("%s\n", skip(phrase, k-1)); } return 0; }
/Copyright (C)1999 Lucent Technologies * /From 'Programming Pearls'by Jon Bentley * /markovhash.c --generate random text,sped up with hash tables * /For storage efficiency (and also to minimize changes from markov.c), the hash table is implemented in the integer array next. If bin[i]=j,then word[j]is the first element in the list, word[next[j]]is the next element,and so on. #include <stdio.h> #include <stdlib.h> #include <string.h> char inputchars [4300000]; #define MAXWORDS 800000 char *word [MAXWORDS]; int nword =0; int k 2; int next [MAXWORDS]; #define NHASH 499979 int bin [NHASH]; #define MULT 31 unsigned int hash(char *ptr) { unsigned int h 0; unsigned char *p ptr; int n; for (n k;n 0;p++){ h MULT h *p; if(*p=0) n--; return h号NHASH; int wordncmp (char *p,char*q) int n k; for（;*卫p==*q;p++,q++) 1f(*p=0&&--n==0) return 0; return *p -*q; int sortcmp(char **p,char **q) { return wordncmp(*p,*q); char *skip(char *p,int n) { for(;n>0;p++) if(*p==0)】 n--; return p; int main() int i,wordsleft 10000,j; char *phrase,*pi word [0]inputchars; while(scanf("号s",word[nword])！=EoE){
/* Copyright (C) 1999 Lucent Technologies */ /* From 'Programming Pearls' by Jon Bentley */ /* markovhash.c -- generate random text, sped up with hash tables */ /* For storage efficiency (and also to minimize changes from markov.c), the hash table is implemented in the integer array next. If bin[i]=j, then word[j] is the first element in the list, word[next[j]] is the next element, and so on. */ #include <stdio.h> #include <stdlib.h> #include <string.h> char inputchars[4300000]; #define MAXWORDS 800000 char *word[MAXWORDS]; int nword = 0; int k = 2; int next[MAXWORDS]; #define NHASH 499979 int bin[NHASH]; #define MULT 31 unsigned int hash(char *ptr) { unsigned int h = 0; unsigned char *p = ptr; int n; for (n = k; n > 0; p++) { h = MULT * h + *p; if (*p == 0) n--; } return h % NHASH; } int wordncmp(char *p, char* q) { int n = k; for ( ; *p == *q; p++, q++) if (*p == 0 && --n == 0) return 0; return *p - *q; } int sortcmp(char **p, char **q) { return wordncmp(*p, *q); } char *skip(char *p, int n) { for ( ; n > 0; p++) if (*p == 0) n--; return p; } int main() { int i, wordsleft = 10000, j; char *phrase, *p; word[0] = inputchars; while (scanf("%s", word[nword]) != EOF) {
word[nword+1]word[nword]strlen(word[nword])+1; nword++; for (i=0;i k;i++) word[nword][i]0; for (i=0;i<NHASH;i++) bin[i]=-1; for (i=0;i <nword -k;i++){/check * j=hash(word[i]); next [i]bin[j]; bin[j]=i; } for (i=0;i<k;i++) printf("s\n",word[i]); phrase inputchars; for wordsleft 0;wordsleft--){ 1=0； for (j =bin[hash(phrase)];j>=0;j=next[j]) if ((wordncmp(phrase,word[j])==0) &&(rand()号(++i)==0)) p word[j]; phrase skip(p,1); if (strlen(skip(phrase,k-1))==0) break; printf("s\n",skip(phrase,k-1)); } return 0;
word[nword+1] = word[nword] + strlen(word[nword]) + 1; nword++; } for (i = 0; i < k; i++) word[nword][i] = 0; for (i = 0; i < NHASH; i++) bin[i] = -1; for (i = 0; i <= nword - k; i++) { /* check */ j = hash(word[i]); next[i] = bin[j]; bin[j] = i; } for (i = 0; i < k; i++) printf("%s\n", word[i]); phrase = inputchars; for ( ; wordsleft > 0; wordsleft--) { i = 0; for (j = bin[hash(phrase)]; j >= 0; j = next[j]) if ((wordncmp(phrase, word[j]) == 0) && (rand() % (++i) == 0)) p = word[j]; phrase = skip(p, 1); if (strlen(skip(phrase, k-1)) == 0) break; printf("%s\n", skip(phrase, k-1)); } return 0; }