알고리즘 특론(과제 3)
- 최초 등록일
- 2012.01.17
- 최종 저작일
- 2010.09
- 3페이지/ 한컴오피스
- 가격 1,500원
소개글
0000대학교 컴퓨터 전공 관련 과목 수강시 작성한 보고서입니다.
알고리즘 특론 과제 중 하나입니다.
세부내용은 목차를 참조 바랍니다.
목차
1. (5, 18, 31, 17, 2, 15, 13)의 키들을 이 순서대로 크기 11의 빈 해시 테이블에 이중 해싱법으로 삽입하는 과정을 보이시오.
2. 텍스트 T와 패턴 P가 다음과 같이 주어졌을 때 보이어 무어 알고리즘에 의한 패턴 매칭 과정을 보이시오.
3. 패턴 집합이 다음과 같이 주어졌을 때 Aho-Corasick 알고리즘을 적용하기 위한 단어 나무를 만드시오.
....
본문내용
3. 패턴 집합이 다음과 같이 주어졌을 때 Aho-Corasick 알고리즘을 적용하기 위한 단어 나무를 만드시오. {double, done, undo, unit, universe}
* 단어 나무의 정의
패턴의 집합 P=P1,P2,···Pq에 대한 단어 나무 W는 뿌리 나무로서 다음의 세 조건을 만족한다.
1) 모든 간선은 하나의 문자로 레이블 된다.
2) 동일 노드에서 나가는 둘 이상의 간선은 서로 다른 문자로 레이블 된다.
3) W의 뿌리 r로부터 어떤 노드 x까지에 이르는 경로상의 문자들을 차례로 접속한 것을 word(x)라 하면 word(x)는 어떤 P1의 접두부로 된다. 또 각 P1⊂P에 대하여 P1=word(v)인 노드 v가 W에 존재한다. 잎 노드 x의 word(x)는 반드시 어떤 P1와 같아야 한다.
참고 자료
없음