The Prague Stringology Conference 2009

Kazunori Hirashima, Hideo Bannai, Wataru Matsubara, Akira Ishino and Ayumi Shinohara

Bit-parallel algorithms for computing all the runs in a string

Abstract:
We present three bit-parallel algorithms for computing all the runs in a string. The algorithms are very efficient especially for computing all runs of short binary strings, allowing us to run the algorithm for all binary strings of length up to 47 in a few days, using a PC with the help of GPGPU. We also present some related statistics found from the results.

Download article: Article in PostScript Article in PDF BibTeX Reference
 PostScript   PDF   BibTeX reference 
Download presentation: Presentation