[quoting order normalized -dM]

>> I'm not sure which algorithm I'm using in terms of names like those.
>> The name Boyer/Moore comes to mind, but I'm not sure exactly what
>> that is so I could be misled there.
> There is even Boyer-Moore string search implementation in tree -
> bm(3).

I just read over bm.c.

The algorithm therein looks related to mine, but definitely isn't the
same.  In particular, I don't have the frequency table (such a thing
could improve efficiency of mine in cases where certain characters
occur _very_ much more frequently than others, but to do it right would
greatly complicate the computation of the table), and searching doesn't
need the fast-loop/slow-loop split in the search function.

My code is small enough that I'll just quote it here.  I've left off an
#include, but all it does is prototype searchstr_maketbl() and
searchstr().

I place this code in the public domain.  Feel free to pick it up for
anything you want.

static int eq(const unsigned char *s1, const unsigned char *s2, int n, const char *eqv)
{
 for (;n>0;n--) if (eqv[*s1++] != eqv[*s2++]) return(0);
 return(1);
}

void searchstr_maketbl(unsigned char (*tbl)[256], const unsigned char *str, unsigned int len, const unsigned char equiv[256])
{
 const unsigned char *str1;
 int i;
 int j;
 int k;
 int l;

 if (len < 1) return;
 str1 = str + 1;
 for (i=len-1;i>=0;i--)
  { l = len - 1 - i;
    for (j=255;j>=0;j--)
     { for (k=i;k>=0;k--)
	{ if ((equiv[str[k]] == equiv[j]) && ((l == 0) || (k == i) || eq(str1+k,str1+i,l,equiv)))
	   { tbl[i][j] = i - k;
	     break;
	   }
	}
       if (k < 0)
	{ for (k=0;k<l;k++)
	   { if (eq(str,str1+i+k,l-k,equiv))
	      { tbl[i][j] = 1 + i + k;
		break;
	      }
	   }
	  if (k >= l) tbl[i][j] = len;
	}
     }
  }
}

int searchstr(const unsigned char *str, unsigned int len, unsigned char (*tbl)[256], unsigned int tbllen)
{
 unsigned int strpos;
 unsigned int stridx;
 unsigned int stroff;
 unsigned int adv;

 strpos = 0;
 while (1)
  { stroff = tbllen - 1;
    stridx = strpos + stroff;
    if (stridx >= len) return(-1);
    while (1)
     { adv = tbl[stroff][str[stridx]];
       if (adv == 0)
	{ if (stroff == 0)
	   { return(stridx);
	   }
	  stroff --;
	  stridx --;
	}
       else
	{ strpos += adv;
	  break;
	}
     }
  }
}

/~\ The ASCII				der Mouse
\ / Ribbon Campaign
 X  Against HTML	       mouse@rodents.montreal.qc.ca
/ \ Email!	     7D C8 61 52 5D E7 2D 39  4E F1 31 3E E8 B3 27 4B