All Pairs Suffix-Prefix Matches using Enhanced Suffix Array
Anindya Das, Rajdeep Baruri · 2020 International Conference on Smart Electronics and Communication (ICOSEC) · 2020
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(m2) time and space complexity, where m and n are the total number and total length of all input strings, respectively.