Circular Pattern Discovery
Jie Lin, Yue Jiang, Donald Adjeroh · The Computer Journal · 2014
Given a text or database T, the circular pattern discovery (CPD) problem is to identify ‘interesting’ circular patterns in T. Here, no specific input pattern is provided, and what is interesting is typically defined in terms of constraints in the search. We propose two algorithms for the CPD problem. The first algorithm uses suffix trees and suffix links to solve the exact CPD problem in time, where m2 is the maximum length of the circular patterns and N is the total length of the sequence database. The second algorithm uses suffix arrays to solve the more challenging approximate CPD (ACPD) problem in worst case, and on average, where k is the maximum allowed error(s). By exploiting the nature of the ACPD problem, the complexity is reduced to time in the worst case, and on average.