Notice
Recent Posts
Recent Comments
Link
«   2025/02   »
일 월 화 수 목 금 토
1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28
Tags more
Archives
Today
Total
관리 메뉴

목록KMP 동작방식 (1)

JIE0025

[문자열 매칭] KMP (knuth-morris-prett) 동작방식,수도코드

✅ 개요문자열 매칭 알고리즘 중 O(N+M)을 보장하는, KMP 알고리즘의 원리를 알아보자. ✅ 단순 문자열 매칭의 비효율가장 단순하게 문자열 매칭을 해보면 아래와 같은 수도 코드가 된다. 2중 for문을 사용하게 되어서 만약 찾고자 하는 패턴이, 문자열의 마지막에 존재하게 되면 최악의 케이스는 O(N*M)이 된다. 단순 문자열 비교는 너무나 비효율적이고, 모든 경우를 다 비교하지 않기 위해 문자열 매칭 알고리즘들이 존재한다. ✅ KMP (Knuth-Morris-Pratt)오늘 공부해볼 알고리즘은 KMP이다. KMP는 접두사/접미사의 개념을 활용해 1) 모든 경우를 계산하지 않고 2) 반복되는 연산을 줄인다 🕰 시간복잡도 : O(N+M)N : text 문자열의 길이M : 패턴 문자열의 길이 1️⃣ 테이블..
Algorithm 2023. 6. 1. 23:42
이전 Prev 1 Next 다음