A Linear-time Algorithm for the Longest Common Nonsuperstring Problem Using Generalized Suffix Arrays
Suk-Hyeun Cho, Hyun-Chul Yoon, Joong-Chae Na, Jeong Seop Sim · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2011
Given a set F of strings over constant size alphabet , the common nonsuperstring of F is a string that is not a superstring of any string in F. Among the common nonsuperstrings of F, the longest one with finite length is the longest common non superstring of F. Recently, two O()-time algorithms for finding the longest common nonsuperstring were proposed where denotes the sum of the lengths of the strings in F. One algorithm was based on the suffix graph model and the other was based on the prefix graph model. Especially, the former algorithm used generalized suffix trees to construct the suffix graph model. In this paper, we propose another linear-time algorithm based on suffix graph model. Our algorithm uses generalized suffix arrays to construct the suffix graph model. Also, we propose some experimental results to show the performance of our algorithm.