문자열의 근사커버 찾기 = Finding Approximate Covers of Strings

다국어 초록 (Multilingual Abstract)

Repetitive strings have been studied in such diverse fields as molecular biology, data compression, etc. Some important regularities that have been studied are periods, covers, seeds and squares. A natural extension of the repetition problems is to allow errors. Among the four notions above, approximate squares and approximate periods have been studied.In this paper, we introduce the notion of approximate covers which is an approximate version of covers. Given two strings P`(|P`|=m)

국문 초록 (Abstract)

반복적인 문자열에 대한 연구는 최근 들어 여러 분야에서 활발히 진행되어 왔다. 특히 DNA 염기서열의 분석 등 분자생물학에서 그 필요성이 대두되고 있다. 주기, 커버, 시드, 스퀘어 등이 반복적인 문자열의 대표적인 예들이다. 근사문자열 매칭 분야에서도 근사주기, 근사스퀘어 등 반복적인 문자열에 관한 연구가 진행되고 있다.본 논문에서는 근사커버의 개념을 제시한다. 길이가 각각 m, `n`