All Pairs Suffix-Prefix Matches using Enhanced Suffix Array

摘要

The problem of ‘all-pairs suffix-prefix overlap’ has been studied earlier using the generalized suffix tree (GST) and generalized suffix array (GSA). An alternative form of generalized enhanced suffix array (GESA), name Alternative-GESA or AGESA was introduced and used to compute suffix-prefix-overlap. This study didn’t consider multiple sentinel character in Alternative-GESA. It also exploited how to use AGESA without sentinel characters for the ‘all-pair suffix-prefix overlap’ problem. In this approach, proposed algorithms utilized the advantage of locality-of-reference for matching suffixes, those occur enough apart in actual GSA or GESA due to the high ASCII value of sentinel characters. All-pairs suffix-prefix overlap was computed in $O(n)+o(m^{2})$ time and space complexity, where m and n are the total number and total length of all input strings, respectively.