Constant Time RMESH Algorithm for Finding All-pairs Suffix-prefix Matching of Strings (문자열의 suffix-prefix가 일치하는 모든 쌍 찾기를 위한 상수시간 RMESH 알고리즘 )

Jinwoon Woo (우진운)

Constant Time RMESH Algorithm for Finding All-pairs Suffix-prefix Matching of Strings

Journal of Knowledge Information Technology and Systems
Abbr : JKITS
2011, 6(3), pp.161-170
Publisher : Korea Knowledge Information Technology Society
Research Area : Interdisciplinary Studies > Interdisciplinary Research
Published : June 30, 2011

Jinwoon Woo ¹

¹단국대학교

Candidate

ABSTRACT

Since string operations were applied to computational biology area, 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 present an algorithm to find all-pairs suffix-prefix matchings of the given strings using three-dimensional processors on RMESH(Reconfigurable MESH). The algorithm has time complexity.

KEYWORDS

string, suffix-prefix matching, string matching, RMESH, time complexity

Citation status

* References for papers published after 2023 are currently being built.

[journal] 김경훈 / 2004 / Constant Time Algorithm for Alignment of Unaligned Linear Quadtrees on RMESH / 정보과학회논문지 : 시스템 및 이론 / 한국정보과학회 31(1) : 10~18

[journal] 우진운 / 2010 / Constant Time RMESH Algorithm for Finding Maximal Palindromes of String / 한국지식정보기술학회 논문지 / 한국지식정보기술학회 5(2) : 59~67

[journal] 이상구 / 2010 / A High-Speed Parallel Fuzzy Controller with new COG Method Using OpenMP / 한국지식정보기술학회 논문지 / 한국지식정보기술학회 5(1) : 77~84

[journal] 한선미 / 2009 / Constant Time RMESH Algorithm for Computing Longest Common Substring and Maximal Repeat of String / 정보처리학회논문지. 컴퓨터 및 통신시스템 / 한국정보처리학회 16(5) : 319~326

[journal] 우진운 / 2010 / Finding All-Pairs Suffix-Prefix Matching Using Suffix Array / 정보처리학회논문지. 컴퓨터 및 통신시스템 / 한국정보처리학회 17(5) : 221~228

[journal] A. Apostolico / 1988 / Parallel Construction of a Suffix Tree with Application / Algorithmica 3 : 347~365

[book] D. Gusfield / 1997 / Algorithms on Strings, Trees, and Sequences, In Computer Science and Computational Biology / CamBridge University Press

[journal] G. Landau / 1989 / Fast parallel and serial approximate string matching / J. of Algorithms 10 : 157~169

[confproc] H. Lee / 1997 / RMESH Algorithms for Parallel String Matching / International Symposium on Parallel Architectures, Algorithms and Networks : 223~226

[journal] J. Jang / 1995 / A Fast Algorithm for Computing Histogram on a Reconfigurable Mesh / IEEE Trans. on Pattern Analysis and Machine Intelligence 17(2) : 97~106

[confproc] M. Nigam / 1993 / Sorting n Numbers On Reconfigurable Meshes With Buses / Proceedings 7th Intern`ational Parallel Processing Symposium : 174~181

[journal] P. Green / 1993 / Ancient conserved regions in new gene sequences and the protein databases / Science 259 : 1711~1716

[journal] R. A. Wagner, Michael / 1974 / The String-to-String Correction Problem / Journal of the ACM (JACM) 21(1) : 168~173

[journal] R. Miller / 1993 / Parallel Computation on Reconfigurable Meshes / IEEE Transactions on Computers 42(6) : 678~692

[journal] W. Masek / 1980 / A fast algorithm computing string edit distances / J. of Computer and System Sciences 20(1) : 13~31

[journal] Z. Galil / 1995 / A Constant Time Optimal Parallel String Matching Algorithm / J. of ACM 42 : 908~918

[journal] Z. M. Kedem / 1996 / Parallel suffix-prefix-Matching Algorithm and Applications / SIAM Journal on Computing 25(5) : 998~1023

KJCKorea
Journal Central

Journal of Knowledge Information Technology and Systems 2023 KCI Impact Factor : 0.89