TY  - JOUR
T1  - Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets
AU  - Kim, Youngho 
AU  - Sim, Jeong Seop 
JO  - Journal of KIISE, JOK
PY  - 2017
DA  - 2017/1/14
DO  - 10.5626/JOK.2017.44.8.760
KW  - CUDA
KW  - repetitive strings
KW  - approximate string matching
KW  - parallel algorithm
AB  - Repetitive strings have been studied in diverse fields such as data compression, bioinformatics and so on. Recently, two problems of approximate periods of strings over integer alphabets were introduced, finding minimum δ-approximate periods and finding minimum γ-approximate periods. Both problems can be solved in O(n²) time when n is the length of the string. In this paper, we present two parallel algorithms for solving the above two problems in O(n²) time using O(n²) threads, respectively. The experimental results show that our parallel algorithms for finding minimum δ-approximate (resp. γ-approximate) periods run approximately 19.7 (resp. 40.08) times faster than the sequential algorithms when n = 10,000.