/* Pattern word filter for CS 638.
   Eric Bach 11/30/98

   Usage: 
                pattern ABACDE < /usr/dict/words 

   selects all words matching the pattern.  Patterns can be 
   any string of letters.

   This program is case sensitive.  If you don't want this,
   pipe the dictionary through

        tr "a-z" "A-Z"

   first.

*/

#include <stdio.h>

#define MAXWORD 100
#define NUMCHARS 256

char P[MAXWORD];        /* Pattern */
int  Plen;

char W[MAXWORD];        /* Current word */
int  Wlen;

standardize(P, Plen)  /* Put P into standard form, e.g. THAT --> ABCA */
char P[];
int Plen;
{
char S[MAXWORD];    /* pattern in standard form */
char T[NUMCHARS];   /* translation table */
int i;
char next;
for (i=0;i<NUMCHARS;i++) T[i] = '\0';
i = 0;
next = 'A';
while (P[i]) {
        if (T[P[i]]) S[i] = T[P[i]];
        else {
             S[i] = next;
             T[P[i]] = next;
             next++;
             }
        i++;
        }
for (i=0;i<Plen;i++) P[i] = S[i];
}

test(W,Wlen)    /* See if W has the form P. O(n^2) -- can we do better? */
char W[];
int Wlen;
{
int i,j;
char assigned;
if (Wlen != Plen) return(0);
assigned = 'A'-1;
for (i=0;i<Plen;i++) {
    /* printf("%d %c %c %c\n",i,P[i],W[i], assigned); */
    if (P[i] <= assigned) {
        for (j=0;j<i;j++) if (P[j] == P[i]) break;
        if (W[i] != W[j]) return(0);
        }
    else {
        assigned++;
        for (j=0;j<i;j++) if (W[j] == W[i]) return(0);
        }
    }
return(1);
}

main(argc, argv)
int argc;
char *argv[];
{
char c;
int i;

if (argc != 2) {
        printf("use: pattern ABABCD \n");
        exit();
        }
else sscanf(argv[1],"%s",P);

Plen = 0;
while (P[Plen]) Plen++;

standardize(P,Plen);

/* printf("%s length %d\n",P, Plen); */

for (;;) {
        if ((c = getchar()) == EOF) break;
        W[0] = c; 
        i=1;
        while ((c = getchar()) != '\n') W[i++] = c;
        W[i] = '\0';
        Wlen = i;
        if (test(W,Wlen)) printf("%s\n",W);
        }
}