[자료구조]Pattern Matching 프로그램

소개글

어떤 string set 내에서 일정한 패턴의 위치를 찾아내는 프로그램의 설계와 구현에 대한 내용입니다. hash table과 AVL tree에 대한 설명과 구현, 실제 응용에 대해서 나와있습니다.

목차

I. 요구조건
1. 개요
2. spec 및 사용자 설명서

II. 설계
1. Hash Table
2. AVL Tree(Adelson-Velskii and Landis Tree)
3. Pattern Matching

III. 영향 및 평가
1. 성능 평가
2. 배운 점
3. 알려진 버그와 한계

본문내용

Pattern Matching 은 Hash table, AVL tree, Linked List 등의 여러 가지 자료구조를 사용해서, 어떤 String Set 내에서의 일정한 Pattern의 위치를 찾아내는 프로그램입니다.
전체 String의 수가 n일 때 String 전체의 집합을 S={S1, S2, .., Sn} 이라고 하고, 이것은 data file을 통해 한 줄에 하나씩 입력받습니다. String Si 의 길이가 k라면, substring의 길이 k에 대해 Si[1...k], ... Si[m-k+1...m] 의 substring이 존재합니다. 이 프로그램에서는 k=6인 substring들을 구하고, 이 substring과 그 위치에 대해 Hash table을 만들고, 입력 받은 pattern을 이를 통해 검색해서 출력합니다.

참고 자료

없음