#
@M

Knuth-Morris-Pratt 알고리즘

  • 문자열 내에서 특정 문자열을 찾는 매칭 알고리즘.
  • 단순히 나이브하게 브루트포스로 문자열을 찾는다면:
    S = "ABCDABCDABEE"
W = "ABCDABE"

cnt = 0

for s in S:
  cnt += 1
  for w in W:
    if s != w:
      cnt -= 1
      break
    • 원본 문자열 길이가 NN, 찾을 문자열 길이가 MM일 때 시간복잡도는 O(NM)O(NM).
    • 탐색하지 않아도 될 부분에서 불필요한 탐색을 하고 있음:
      A B C D A B C D A B E E
A B C D A B X           (i=0)
  X X X X X X X         (i=1)
    X X X X X X X       (i=2)
      X X X X X X X     (i=3)
        A B C D A B E   (i=4)
          X X X X X X E (i=5)
  • KMP 알고리즘은 불필요한 탐색을 줄이기 위해 만들어졌다.

접두사와 접미사

  • LPS 테이블을 만든다.
  • ABCDABE의 LPS 테이블:
    A        0
AB       0
ABC      0
ABCD     0
ABCDA    0
ABCDAB   2 (AB == AB)
ABCDABE  0

이 문서를 인용한 문서