, .. , . , , () , .
. , , .
int BFSearch(char *s, char *p)
{
for (int i = 1; strlen(s) - strlen(p); i++)
{
for (int j = 1; strlen(p); j++)
{
if (p[j]!= s[i+j-1])
{
break;
}
else
{
if (j = strlen(p))
{
return(i);
exit;
}
}
}
}
}
BFSearch p s 0, . , , , .
, , -, (Robert S. Boyer) (J. Strother Moore), .
-
- . . . . , , , , . , .. , . - ( ) , . , , .
: , , . , , . , , , .
|
|
|
, , . . : a, b, c, d, e abbad abeccacbadbabbad. :
abbad.
. . 5 :
, . :
. 2 :
2 :
, , , :
. , . , 256 , :
struct BMTable
{
int bmtarr[255];
} *bmt;
, p.
BMTable MakeBMTable(char *p)
{
int i;
for (i = 0; i <= 255; i++) bmt->bmtarr[i] = strlen(p);
for (i = strlen(p); i <= 1; i--)
{
if (bmt->bmtarr[p[i]] == strlen(p))
{
bmt->bmtarr[p[i]] = strlen(p)-i;
}
}
return(*bmt);
}
, .
int BMSearch(int startpos, char *s, char *p)
{
int pos, lp, i;
lp = strlen(p);
pos = startpos + lp - 1;
while (pos < strlen(s))
{
if (p[lp]!= s[pos]) pos = pos + bmt->bmtarr[s[pos]];
else
{
for (i = lp - 1; i <= 1; i--)
{
if (p[i]!= s[pos - lp + i])
{
pos++;
break;
}
else
if (i = 1)
{
return(pos - lp + 1);
exit;
}
}
}
}
return(0);
}
BMSearch p s. p s , 0. startpos s, . , p s. startpos 1. , , p s, startpos .
()
, , , .
lb ub , , , . . , , . , ub (m 1) . , . , 100 , 50 , 25, 13, 7 .. n, log2n .
|
|
|
int BinarySearch (int lb, int ub, int key, int* pArr)
/* a , lb , ub , key . , -1 */
{
int m;
return(-1); // -1,
do
{
m = (lb + ub)/2; //
if (key < pArr[m]) ub = m-1;
else
if (key > pArr[m]) lb = m+1;
else
{ //
return(m);
break;
}
}
while (lb > ub);
}
