[질문] kmp 최적화포인트 질문

[익명(61.74)]

O(NM)의 나이브한 문자열 서칭과 비교했을 때,

KMP는 불일치 발생 시 그 앞의 마지막으로 일치한 문자로 끝나는 최장접미사가 있으면 동일한 크기, 동일한 내용의 최장접두사의 이후부터 비교해보면 된다는 게 유일한 최적화 포인트임?

[Miyano(skeep194)]

맞워요 그거로 O(N)이 보장되는거임 그리고 kmp는 실패 함수 자체도 쓸일이 있으니 어쨌든 알아두면 좋다

[익명(14.53)]

ㅇㅇ 존나 스마트하게 확인하는거