Fast algorithms for single and multiple pattern Cartesian tree matching - Theoretical Computer Science에 논문 게재

본 논문에서는 generalized matching 문제 중 하나인 Cartesian tree matching 문제를 빠르게 해결하는 알고리즘을 제시하였다.

주어진 pattern과 text를 0과 1로 이루어진 binary 문자열로 바꿔 기존의 string matching을 사용하여 matching이 일어날 수 있는 위치를 찾는 binary filtration과 각 위치가 답이 되는 지 효율적으로 확인할 수 있는 verification technique을 통해 기존 알고리즘보다 평균 38배의 성능향상을 달성할 수 있었다.

또한 여러 개의 pattern을 찾는 문제에 대해서도 fingerprinting method와 기존의 multiple string matching 알고리즘을 결합하여 보다 효율적인 알고리즘을 제시하였다.

(https://www.sciencedirect.com/science/article/pii/S0304397520305806)

이 논문은 과기정통부의 재원으로 한국연구재단 바이오․의료기술개발사업의 지원을 받아 수행된 연구이다.