Skip to content


Algorithms based on Packed String Matching

In the packed string matching technique multiple characters are packed into one larger word, so that the characters can be compared in bulk rather than individually. In this context, if the characters of a string are drawn from an alphabet of size σσ, then wlogσ\lfloor \frac{w}{\log σ} \rfloor different characters fit in a single word, using logσ\lceil \log σ \rceil bits per characters. The packing factor is α=wlogσα = \lfloor \frac{w}{\log σ} \rfloor