δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets

Youngho Kim, Jeong Seop Sim

http://doi.org/

(δ, γ)-matching for strings over integer alphabets can be applied to such fields as musical melody and share prices on stock markets. In this paper, we define δ-approximate periods and γ-approximate periods of strings over integer alphabets. We also present two O(n²) - time algorithms, each of which finds minimum δ-approximate periods and minimum γ-approximate periods, respectively. Then, we provide the experimental results of execution times of both algorithms.