Bit-Parallel Algorithms for Exact Circular String Matching
K.-H. Chen, Guan Shieng Huang, R.C.T. Lee · The Computer Journal · 2013
In this paper, we deal with the exact circular string matching problem (abbreviated as ECSM). Given a string P = p1p2 ⋯ pm, a string P(i) = pipi+1 ⋯ pmp1 ⋯ pi−1, for 1 ≤ i ≤ m, is a circular string of P. Given a text string T = t1t2 ⋯ tn and a pattern P, the ECSM problem is to find all occurrences of P(i) in text T for 1 ≤ i ≤ m. This paper proposes two algorithms that perform searching of a circular string on text using the bit-parallel technique. Our algorithms use only the composition of bitwise-logical operations and basic arithmetic operations, and apply this technique to solve the problem. These algorithms are given names CSBNDM and CSBNDNq, respectively. We give several experiments to verify that they have good performance for random strings and DNA sequences.