1장. 문자열학의 기초
2장. 조합론적 퍼즐
__1 페르마의 작은 정리의 문자열학적인 증명
__2 부호성 검사의 간단한 경우
__3 마방진과 투에 - 모스 단어
__4 올덴버거 - 콜라코스키 수열
__5 제곱이 없는 게임
__6 피보나치 단어와 피보나치 기수법
__7 와이트호프의 게임과 피보나치 단어
__8 서로 다른 주기적 단어
__9 투에 - 모스 단어의 친척
__10 투에 - 모스 단어와 거듭제곱의 합
__11 단어의 켤레와 회전
__12 켤레 회문
__13 많은 회문을 갖는 많은 단어
__14 순열의 짧은 초단어
__15 순열의 짧은 초수열
__16 스콜렘 단어
__17 랭포드 단어
__18 린던 단어에서 드 브루인 단어로
3장. 패턴 찾기
__19 경계표
__20 가장 짧은 덮개
__21 짧은 경계
__22 접두어 표
__23 최대 접미어로 향하는 경계표
__24 주기성 검사
__25 엄격한 경계
__26 순차적 문자열 탐색의 지연
__27 희박한 탐색 자동자
__28 효율적으로 비교하는 문자열 탐색
__29 피보나치 단어의 엄격한 경계표
__30 싱글톤 변수를 갖는 단어
__31 순서 보존 패턴
__32 매개변수화된 탐색
__33 좋은 접미어 표
__34 보이어-무어 알고리듬의 최악의 경우
__35 초고속 BM 알고리듬
__36 와일드카드를 갖는 문자열 탐색
__37 순환적 등가
__38 간단한 최대 접미어 계산
__39 자기최대 단어
__40 최대 접미어와 그 주기
__41 단어의 임계 위치
__42 린던 단어 접두어의 주기
__43 지민 단어를 찾아서
__44 불규칙적인 2차원 패턴 검색
4장. 효율적 자료 구조
__45 최단 덮개에 대한 리스트 알고리듬
__46 최장 공통 접두어 계산
__47 접미어 배열에서 접미어 나무로
__48 선형 접미어 트라이
__49 삼진 검색 트라이
__50 두 단어의 최장 공통 인자
__51 부분문자열 자
이 책의 대상 독자
자료 구조와 알고리듬에 관한 대학원 수업을 가르치는 교수자는 수강생을 위해 이 책의 원하는 부분을 어디든지 선택할 수 있다. 하지만 기초 교재는 아니며, 연구원, 박사과정 또는 석사과정 대학원생과 문자열 알고리듬에 직접적인 연관이 없더라도 알고리듬 수업을 강의해야 하는 학자들을 위한 참고자료로 집필했다. 이 책은 이 분야의 표준 교재에 대한 참고자료라고 생각해야 한다. 문제에 포함된 설명은 이 주제에 대한 깊은 배경지식을 요구하지 않고 그 이해와 해법에 대한 빠른 접근을 제공한다.
이 책의 구성
이 책은 7개의 장으로 구성된다.
1장, ‘문자열학의 기초’는 다음 장을 위한 용어, 기본 개념, 기본 도구를 소개하며 준비하는 장으로, 이 분야의 여섯 가지 큰 줄기를 반영한다.
2장, ‘조합론적 퍼즐’은 단어에 대한 조합 문제에 대한 장으로, 많은 알고리듬이 그 입력의 조합론적 성질에 기반하기 때문에 중요한 주제다.
3장, ‘패턴 찾기’에서는 가장 고전적인 주제인 문서 탐색과 문자열 일치를 다룬다.
4장, ‘효율적 자료 구조’는 문서 색인을 위한 자료 구조에 대해 다룬다. 이 자료 구조는 문서와 관련된 특수한 배열이나 나무와 같은 여러 알고리듬에서 기본적 도구로 사용한다.
5장, ‘단어의 정규성’에서는 단어에서 나타나는 정규성, 특히 반복과 대칭성에 대해 다루며, 알고리듬의 효율성에 큰 영향을 준다.
6장, ‘문자열 압축’은 무손실 문서 압축에서 실질적으로 중요한 영역의 몇 가지 기법을 주로 다룬다.
7장, ‘그 외의 다양한 알고리듬’은 이전 장에 어울리진 않지만, 확실히 알릴 가치가 있는 다양한 문제를 소개한다.
