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 );
}
|