Exact Searching
The bitap algorithm for exact string searching, in full generality, looks like this when implemented in C:
#includeBitap distinguishes itself from other well-known string searching algorithms in its natural mapping onto simple bitwise operations, as in the following modification of the above program. Notice that in this implementation, counterintuitively, each bit with value zero indicates a match, and each bit with value 1 indicates a non-match. The same algorithm can be written with the intuitive semantics for 0 and 1, but in that case we must introduce another instruction into the inner loop to set R |= 1
. In this implementation, we take advantage of the fact that left-shifting a value shifts in zeros on the right, which is precisely the behavior we need.
Notice also that we require CHAR_MAX
additional bitmasks in order to convert the (text == pattern)
condition in the general implementation into bitwise operations. Therefore, the bitap algorithm performs better when applied to inputs over smaller alphabets.
Read more about this topic: Bitap Algorithm
Famous quotes containing the words exact and/or searching:
“His eye had become minutely exact as to the book and its position. Then he resolved that he would not look at the book again, would not turn a glance on it unless it might be when he had made up his mind to reveal its contents.”
—Anthony Trollope (18151882)
“Abode where lost bodies roam each searching for its lost one.”
—Samuel Beckett (19061989)