TY - JOUR

T1 - Fast circular dictionary-matching algorithm

AU - Athar, Tanver

AU - Barton, Carl

AU - Bland, Widmer

AU - Gao, Jia

AU - Iliopoulos, Costas S.

AU - Liu, Chang

AU - Pissis, Solon P.

PY - 2017/2/1

Y1 - 2017/2/1

N2 - Circular string matching is a problem which naturally arises in many contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal worst-and average-case algorithms for circular string matching. Here, we present a suboptimal average-case algorithm for circular string matching requiring time O(n) and space O(m). The importance of our contribution is underlined by the fact that the proposed algorithm can be easily adapted to deal with circular dictionary matching. In particular, we show how the circular dictionary-matching problem can be solved in average-case time O(n + M) and space O(M), where M is the total length of the dictionary patterns, assuming that the shortest pattern is sufficiently long. Moreover, the presented average-case algorithms and other worst-case approaches were also implemented. Experimental results, using real and synthetic data, demonstrate that the implementation of the presented algorithms can accelerate the computations by more than a factor of two compared to the corresponding implementation of other approaches.

AB - Circular string matching is a problem which naturally arises in many contexts. It consists in finding all occurrences of the rotations of a pattern of length m in a text of length n. There exist optimal worst-and average-case algorithms for circular string matching. Here, we present a suboptimal average-case algorithm for circular string matching requiring time O(n) and space O(m). The importance of our contribution is underlined by the fact that the proposed algorithm can be easily adapted to deal with circular dictionary matching. In particular, we show how the circular dictionary-matching problem can be solved in average-case time O(n + M) and space O(M), where M is the total length of the dictionary patterns, assuming that the shortest pattern is sufficiently long. Moreover, the presented average-case algorithms and other worst-case approaches were also implemented. Experimental results, using real and synthetic data, demonstrate that the implementation of the presented algorithms can accelerate the computations by more than a factor of two compared to the corresponding implementation of other approaches.

UR - http://www.scopus.com/inward/record.url?scp=84929009091&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84929009091&partnerID=8YFLogxK

U2 - 10.1017/S0960129515000134

DO - 10.1017/S0960129515000134

M3 - Article

AN - SCOPUS:84929009091

SN - 0960-1295

VL - 27

SP - 143

EP - 156

JO - Mathematical Structures in Computer Science

JF - Mathematical Structures in Computer Science

IS - 2

ER -