논문내용 |
문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. 최대 palindrome을 구하는 문제는 주어진 문자열에서 좌우 대칭인 최대 부분문자열을 찾는 연산이다. 이 연산은 패턴 매칭, 유사도 측정 등의 문자열 처리 분야에서 중요하게 사용되고 있다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 프로세서를 사용하여 문자열의 최대 palindrome을 구하는 알고리즘을 제안하며, 이 알고리즘은 시간 복잡도를 갖는다. 상수시간 알고리즘은 대량의 데이터를 처리하는 계산 생물학과 같은 응용 분야에서 유용하게 사용된다. |