최근에 KMP에 관해 이해도가 조금 올랐다.
KMP나 아호코라식과 같은 문자열 매칭은 실패함수를 정의하고 dp같이 이해하면 조금 헷갈린다.
DFA로 변환시켜서 경로 찾기로 문제를 환원하자.
실패함수를 정의하는게 헷갈릴 수 있는데, 아호코라식에서 결국 back edge는 suffix tree에서의 경로와 동일하다.
따라서 일대다 문자열 매칭도 suffix tree로 가능
구현 난이도는 둘이 비슷한거 같고 이해는 아호/kmp가 더 쉽긴 한 듯..?