# Approximate String Matching

• 2026년 8월 26일 알고리즘
  편집 거리 — 비슷하다는 말을 수로 바꾸기

  자리끼리만 맞추는 Hamming 거리는 글자 하나가 빠지면 뒤가 전부 밀려 무너진다. 빈 칸을 허용해 정의한 편집 거리를 표 하나로 채우고, O(NM)보다 빠를 수 없다는 말의 정확한 뜻까지 짚는다.