초록 close

문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. suffix-prefix가 일치하는 모든 쌍 찾기는 두 개 이상의 문자열이 주어질 때 각 쌍의 문자열에 대해 가장 긴 suffix와 일치하는 prefix를 찾는 것으로 가장 짧은 슈퍼스트링을 검출하는 근사 알고리즘에서 사용될 뿐만 아니라 생물정보학, 데이터 압축 분야에서도 중요하게 사용된다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 프로세서를 사용하여 문자열들의 suffix-prefix가 일치하는 모든 쌍 찾기를 위한 알고리즘을 제안하며, 이 알고리즘은 시간 복잡도를 갖는다.


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.