Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
426619 | Information and Computation | 2012 | 10 Pages |
Abstract
We present a novel technique, suitable for bit-parallelism, for representing both the nondeterministic automaton and the nondeterministic suffix automaton of a given string in a more compact way. Our approach is based on a particular factorization of strings which on the average allows to pack in a machine word of w bits automata state configurations for strings of length greater than w. We adapted the Shift-And and BNDM algorithms using our encoding and compared them with the original algorithms. Experimental results show that the new variants are generally faster for long patterns.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics