Finding All-Pairs Suffix-Prefix Matching Using Suffix Array


The KIPS Transactions:PartA, Vol. 17, No. 5, pp. 221-228, Oct. 2010
10.3745/KIPSTA.2010.17.5.221,   PDF Download:

Abstract

Since string operations were applied to computational biology, security and search for Internet, various data structures and algorithms for computing efficient string operations have been studied. The all-pairs suffix-prefix matching is to find the longest suffix and prefix among given strings. The matching algorithm is importantly used for fast approximation algorithm to find the shortest superstring, as well as for bio-informatics and data compressions. In this paper, we propose an algorithm to find all-pairs suffix-prefix matching using the suffix array, which takes time complexity. The suffix array algorithm is proven to be better than the suffix tree algorithm by showing it takes less time and memory through experiments.


Statistics
Show / Hide Statistics

Statistics (Cumulative Counts from September 1st, 2017)
Multiple requests among the same browser session are counted as one view.
If you mouse over a chart, the values of data points will be shown.


Cite this article
[IEEE Style]
S. M. Han and J. W. Woo, "Finding All-Pairs Suffix-Prefix Matching Using Suffix Array," The KIPS Transactions:PartA, vol. 17, no. 5, pp. 221-228, 2010. DOI: 10.3745/KIPSTA.2010.17.5.221.

[ACM Style]
Seon Mi Han and Jn Woon Woo. 2010. Finding All-Pairs Suffix-Prefix Matching Using Suffix Array. The KIPS Transactions:PartA, 17, 5, (2010), 221-228. DOI: 10.3745/KIPSTA.2010.17.5.221.