Constant Time RMESH Algorithm for Computing Longest Common Substring and Maximal Repeat of String


The KIPS Transactions:PartA, Vol. 16, No. 5, pp. 319-326, Oct. 2009
10.3745/KIPSTA.2009.16.5.319,   PDF Download:

Abstract

Since string operations were applied to computational biology area, various data structures and algorithms for computing efficient string operations have been studied. The longest common substring problem is an operation to find the longest matching substring in more than two strings, and maximal repeat of string problem is an operation to find substrings repeated more than once in the given string. These operations are importantly used in the string processing area such as pattern matching and likelihood measurement. In this paper, we present algorithms to compute the longest common substring of two strings and to find the maximal repeat of string using three-dimensional ?×?×? processors on RMESH(Reconfigurable MESH). Our algorithms have (1) time complexity.


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, "Constant Time RMESH Algorithm for Computing Longest Common Substring and Maximal Repeat of String," The KIPS Transactions:PartA, vol. 16, no. 5, pp. 319-326, 2009. DOI: 10.3745/KIPSTA.2009.16.5.319.

[ACM Style]
Seon Mi Han and Jin Woon Woo. 2009. Constant Time RMESH Algorithm for Computing Longest Common Substring and Maximal Repeat of String. The KIPS Transactions:PartA, 16, 5, (2009), 319-326. DOI: 10.3745/KIPSTA.2009.16.5.319.