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


Vol. 16,  No. 5, pp. 319-326, Oct.  2009
10.3745/KIPSTA.2009.16.5.319


PDF
  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
  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.

Forms

Search
(IN TITLE, AUTHOR, ABSTRACT,KEYWORDS)

Advanced Search ▼

POPULAR KEYWORDS
(TOP 10 KEYWORDS)

Recent Publications
(LAST 3 YEARS)

Old Journals

Indexing

All publications of TKIPS is indexed in DOI, EBSCO, Google Scholar, Crossref, and CrossCheck.

TKIPS is also selected as the Journal for Accreditation by NRF (National Research Foundation of Korea).

Related Journals