Computing All Repeats of a Partial Word

Abstract

In this paper, we describe two algorithms to identify the repeating subwords in a given partial word $w_o=w_0[1,\dots ,n]$. The first algorithm uses the suffix tree and the second algorithm uses the valency tree. Both algorithms take linear time to identify the repeating subwords of a partial word.