查看文章

문자열 패턴 매칭 알고리즘은 부분문자열 정보와 불일치 정보를 통해 이동 길이를 계산한다. 부분문자열 정보는 패턴의 비교 순서에 영향을 받고, 패턴의 비교 순서를 정하는 과정에서 수집될 수 있다. 본 논문은 비교순서를 정하는 과정에서 수집된 부분문자열 정보를 고려하여 패턴 비교 순서를 결정하는 향상된 문자열 패턴매칭 알고리즘을 제안한다.

1. 서 론문자열 패턴 매칭 문제는 문자열 T= t1... tn 과 패턴 P= p1... pm 에 대해서 조건 ti+ j-1= pj (1≤ j≤ m) 를 만족하는 모든 위치 i 를 찾는 것이다. 유사 패턴 매칭 문제, 다중 패턴매칭 문제, 병렬 패턴 매칭 문제 등이 위 문제로부터 파생된다. 문자열 패턴 매칭 문제는 지금까지 많은 연구가 진행되어 왔다.