Non-overlapping Counting of String Using Suffix Array
Kyoji Umemura, Yuto Kohara, Nudtawon Yusuk, Ayaka Takamoto, Mitsuo Yoshida · 2018
There are two counting methods of "aa" in "aaa". The first method is overlapping count and this method count two "aa" in "aaa". The overlapping count uses the middle "a" twice. The other method is non-overlapping count which can count only one "aa" in "aaa". Non-overlapping counting uses each character once; therefore, there is only one "aa" in "aaa". In this paper, we provide the formulas to compute non-overlapping count of a string from the overlapping count of the related strings. Because a suffix array is known to be an efficient data structure, to obtain overlapping count of any string we can use suffix array to obtain the non-overlapping count of the given string by the formula which is presented in this paper.