M: 패턴의 길이, N: 텍스트의 길이

해싱

• Chaining
• Open Addressing

문자열 매칭

패턴 매칭

카프 - 라빈 알고리즘

• 패턴의 해시 값과 텍스트 내의 패턴의 길이만큼의 문자열에 대한 해시값 비교
• 최악의 시간복잡도: o(MN)
• 평균 시간복잡도: 선형

KMP 알고리즘

• 시간 복잡도 O(N+M)

보이어 무어 알고리즘

• 오른쪽 끝에서 왼쪽으로 문자열 비교
• 불일치가 일어났을 때 텍스트의 문자에 대해 얼마나 이동해야 하는지 미리 계산
• 최악 O(MN)
• 평균 : O(N)보다 시간 소요가 적음

Trie

문자열의 집합을 표현하는 트리 Retrieval에서 이름을 따옴

접미어 트라이

문자열의 모든 접미어를 Trie로 표현

• 문자열 매칭
• 부분 문자열 매칭
• 최장 공통 부분 문자열

압축된 트라이

노드와 간선을 부분 문자열로 압축함

Trivial 알고리즘

접미어 배열

복잡도 :

• 공간: O(N)
• 시간: O(Nlogn)

  LCP 배열

압축

Run-Length

허프만 코딩