查看文章

요 약각 패턴마다 최적의 패턴 스캔 순서를 찾는다면 스트링 매칭 알고리즘의 성능을 향상시킬 수 있다. 하지만 전처리 시간의 제약 때문에, 기존 스트링 알고리즘들은 미리 정해놓은 패턴 스캔 순서를 사용하였다. 본 논문에서는 평균의 경우에 빠르게 하기 위해 각 패턴마다 패턴 스캔 순서를 결정하는 스트링 매칭 알고리즘을 제안한다. 실험을 통해 이 알고리즘이 DNA 서열에 대하여 기존 스트링 매칭 알고리즘들에 비해평균의 경우 빠르다는 걸 보인다.