All-Against-All Circular Pattern Matching
Jia-Yeu Lin, Donald Adjeroh · The Computer Journal · 2011
Given a text T=T[1 … n] and a circular pattern P=P[1 … m], the circular pattern matching (CPM) problem is to find all occurrences of P in T. We present the first algorithm that exploits suffix links to solve the exact CPM (ECPM) problem in O(n log |Σ|) time and O(n) space, where Σ is the symbol alphabet. Then, we present a q-gram-based algorithm for the approximate CPM (ACPM) problem using the idea of bidirectional edit distance. Our algorithm finds all k-approximate occurrences of P in T. We then extend each algorithm to solve the all-against-all variant of the CPM problem for both exact and k-approximate matches. Although the CPM problem has been studied since the 1980s, this is the first attempt on the all-against-all variant, without using a trivial application of standard CPM algorithms. Given a database S=S1$1S2$2 … SZ$Z of Z sequences, our algorithms solve the all-against-all ACPM problem in O(kmaN) time on average and O(kmmN2) worst case, where k is the error parameter, N=∑Zi=1(|Si|+1), ma=N/Z and mm=maxi=1,2,… Z{|Si|}. Space complexity is O(N). These can be compared with the O(N2malog ma) average and O(N3log mm) worst case time required by the best available ACPM algorithm.