- Published on
`(a+)+$` 이 12글자 입력에 10초가 걸리는 이유가 있다. 정규표현식이라는 60년 된 CS 개념의 진짜 내부 — Thompson의 NFA 구성법, 상태 폭발을 피하는 서브셋 알고리즘, Perl이 시작한 백트래킹 기반 엔진의 편리함과 재앙, Cloudflare를 27분간 다운시킨 2019년 ReDoS 사건, 그리고 Google의 RE2가 왜 백트래킹 없이 모든 정규식을 처리하는지. 매일 쓰는 `match()` 뒤의 알고리즘 여행.