Linear and efficient string matching algorithms based on weak factor recognition
We present a simple and very efficient algorithm for string matching based on the
combination of weak factor recognition and hashing. Despite its quadratic worst-case
running time, our algorithm exhibits a sublinear behaviour. We also propose some practical
improvements of our algorithm and a variant with a linear worst-case time complexity.
Experimental results show that, in most cases, some of the variants of our algorithm obtain
the best running times when compared, under various conditions, against the most effective …
combination of weak factor recognition and hashing. Despite its quadratic worst-case
running time, our algorithm exhibits a sublinear behaviour. We also propose some practical
improvements of our algorithm and a variant with a linear worst-case time complexity.
Experimental results show that, in most cases, some of the variants of our algorithm obtain
the best running times when compared, under various conditions, against the most effective …
We present a simple and very efficient algorithm for string matching based on the combination of weak factor recognition and hashing. Despite its quadratic worst-case running time, our algorithm exhibits a sublinear behaviour. We also propose some practical improvements of our algorithm and a variant with a linear worst-case time complexity. Experimental results show that, in most cases, some of the variants of our algorithm obtain the best running times when compared, under various conditions, against the most effective algorithms present in the literature. For instance, in the case of small alphabets and long patterns, the gain in running time is up to 18%. This makes our proposed algorithm one of the most flexible solutions in practical cases.
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果