[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


Build an automaton which recognizes a string


automata stringautom( pat ) char *pat; { short back, i, st; char ch; automata a; a = (automata)malloc(sizeof(struct automrec)); a->d = MAXCHAR; a->st = strlen(pat)+1; a->nextst = (short **)calloc( a->st, sizeof(short *) ); a->final = (short *)calloc( a->st, sizeof(short) ); for( st=0; st <a->st; st++ ) { a->nextst[st] = (short *)calloc( MAXCHAR, sizeof(short) ); if( st <a->st-2 ) a->nextst[st][pat[st]] = st+1; } a->nextst[a->st-2][pat[a->st-2]] = 1-a->st; /* set final state (with the match length) */ a->final[a->st-1] = a->st-1; /* Set backwards transitions */ for( st=1; st <a->st; st++ ) for( back=st-1; back >= 0; back-- ) { ch = pat[back]; if( a->nextst[st][ch] == 0 ) for( i=1; i<=st; i++ ) if( (st==i || strncmp(pat,pat+i,st-i)==0) && ch== pat[st-i] ) { a->nextst[st][ch] = st-i+1; break; } } return( a ); }

C source (716.straut.c)



© Addison-Wesley Publishing Co. Inc.