728x90
[ Algorithm/ KMP 알고리즘 ]
👨🏻‍💻 programming/◽ 알고리즘2024. 7. 23. 16:39[ Algorithm/ KMP 알고리즘 ]

" Algorithm/ KMP 알고리즘 " 🔸 KMP( Knuth, Morris, Prett ) Algorithm? 대표적인 상수시간 내에 할 수 있는 문자열 검색 알고리즘이다. 명칭은 알고리즘 쓰임새와 상관없이 만든 사람이름이다. 문자열 매칭 알고리즘이라고 부르는게(?) 더 좋을거 같다.  🔸 해답https://www.acmicpc.net/problem/1786"baekjoon 1786번 - 찾기"와 함께 kmp 알고리즘을 배우고 풀어보자. P: 패턴(길이: m) T: 텍스트(길이: n) 만약 모든 매칭을 하나하나 확인한다면? (n - m + 1) x m  = 시간 복잡도 O(nm)목표: 시간 목잡도 O(n) 만들기.  🔥 step 1.  찾으려는 문자열 전처리 과정 거치기 접두사(이을 접 : 接..

728x90
image