您正在查看: 数据结构与算法 分类下的文章

Prefix searching in a PAT array

Prefix searching in a PAT array

 int search( pat, index, n )  
 char *pat, *index[];
 int n; /* size of the PAT array */

{ int m, left, right, low, high, i;

m = strlen(pat);
/* search left end */
if( strncmp( pat, index[], m ) != 1 ) left = 0;
else if( strncmp( pat, index[n-1], m ) == 1 ) left = n;
else { /* binary search /
for( low=0, high=n; high-low > 1; ) {
i = (high+low)/2;
if( strncmp( pat, index[i], m ) != 1 ) high = i;
else low = i;
}
left = high;
}
/
search right end */
if( strncmp( pat, index[], m ) == -1 ) right = -1;
else if( strncmp( pat, index[n-1], m ) != -1 ) right = n-1;
else { /* binary search */
for( low=0, high=n; high-low > 1; ) {
i = (high+low)/2;
if( strncmp( pat, index[i], m ) != -1 ) low = i;
else high = i;
}
right = low;
}
return( right-left+1 );
}

C source (724.srch.c)

Shift-or text searching

Shift-or text searching

char *search( pat, text )
char *pat, *text;

{ int B, bits, i, m, mask[MAXCHAR];

if( pat[

Brute force text searching with k mismatches

Brute force text searching with k mismatches
(Pascal version available)

  char *search( k, pat, text )
  int k;
  char *pat, *text;

{ int j, m, count;

m = strlen(pat);
if( m

String matching with k errors

String matching with k errors

 char *search( k, pat, text, n )/*** at most k errors ***/
 int k, n;
 char *pat, *text;

{int T[MAXPATLEN+1];
int i, j, m, tj, tj1;

m = strlen( pat );
if( m

String matching with k errors

String matching with k errors

  typedef char * ControlDict[K];

typedef FieldIndex struct {
char FieldName; / Field or attribute name /
struct { int first, last; } InvertedField[K];
/
Boundary indices */
}

C source (721.def.c)