KMP 문자열 매칭 알고리즘 C++ 구현과 next 배열 생성 원리
KMP(Knuth-Morris-Pratt) 알고리즘은 문자열 매칭 문제를 해결하는 효율적인 알고리즘으로, 기존의 브루트 포스 방식이 O(n*m)의 시간 복잡도를 가지는 반면, 패턴 문자열을 전처리하여 next 배열을 생성함으로써 O(n+m)의 시간 복잡도로 최적화합니다(여기서 n은 메인 문자열의 길이, m은 패턴 문자열의 길이). 본 글에서는 핵심 원리를 바탕으로 C++ 코드를 통해 KMP 알 ...
6월 12일 22:20에 게시됨