Character Frequency-Based Approach For Searching For Substrings Of Circular Patterns And Their Conjugates In Online Text

A fundamental problem in computational biology is dealing with circular pat-terns. The problem consists of fnding a pattern and its rotations in a database. In this paper, we present two online algorithms. The frst algorithm reports all of the substrings (factors) of a given pattern in an online text. Then, without losing effciency, we extend the algorithm to process the circular rotations of the pattern. For a given pattern P of size M and a text T of size N, the extended algorithm reports all of the locations in the text where a substring of Pc is found where Pc is one of the rotations of P. For an alphabet size σ using O(M) space, the desired goals are achieved in an average O(MN=σ) time, which is O(N) for all patterns with length M ≆ σ. Traditional string-processing algorithms make use of advanced data structures such as suffx trees and automaton. The experimental results we have provided show that basic data structures such as arrays can be used in text-processing algorithms without compromising effciency.