Indexing Circular Patterns

Abstract. This paper deals with the Circular Pattern Matching Problem (CPM). In CPM, we are interested in pattern matching between the text T and the circular pattern C(P) of a given pattern P = P1... Pm. The circular pattern C(P) is formed by concatenating P1 to the right of Pm. We can view C(P) as a set of m patterns starting at positions j ∈ [1..m] and wrapping around the end and if any of these patterns matches T, we find a match for C(P). In this paper, we present two efficient data structures to index circular patterns. This problem has applications in pattern matching in geometric and astronomical data as well as in computer graphics and bioinformatics.