일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
29 | 30 | 31 |
- 백준
- 프로그래머스
- 시나공
- 스프링
- kotlin
- 알고리즘
- 백준알고리즘
- 공부일지
- SQL
- 백준 알고리즘
- programmers
- python
- C++
- MYSQL
- 회고
- 코틀린
- 자바
- 소프티어
- BFS
- 코딩봉사
- 데이터베이스
- 1과목
- 정보처리산업기사
- SW봉사
- softeer
- CJ UNIT
- 코딩교육봉사
- 문제풀이
- 파이썬
- java
- Today
- Total
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️⃣ 테이블에 정보 저장
접두사이면서 접미사인 문자열의 최대 길이를 저장하는 테이블을 미리 정의한다.
(불일치가 발생했을때,, 패턴이 어디까지 일치했는지 보고, 다음 시작 위치를 말해주는 테이블이다.)
검색할 패턴이 abacaaba라고 가정했을 때
각 index 까지 접두사이면서 접미사인 최대 길이를 배열에 저장한다
table[7]의 경우엔 abacaaba에서
aba가 가장 긴 접두사이면서 접미사이므로
해당 길이인 3이 저장된다
2️⃣ 작동과정의 시각화
검색대상 문자열이 ababacabacaaba라고하고,
검색할 패턴이 abacaaba라고 가정하자.
table에는 아까 저장한 0 0 1 0 1 1 2 3 이 저장되어있다.
수도 코드를 함께 보면서 이해하길 바란다.
✍️ pattern과 비교했을때,, 지금까지 몇개가 일치하는가? -> idx 에 저장
for문 -- text의 길이만큼 반복을 한다.
text의 처음부터 매칭을 시작한다.
idx는 0인상태로 시작하고, 매칭 실패할때까지 idx는 1 증가한다.
첫번째 불일치는 idx 가 3인 상황에서 발생했다.
idx는 0보다 크면서 불일치가 발생했으므로,
table[idx-1]의 값을 idx로 넣는다
확인해보면 table[3-1] = table[2]는 1인데
1이라는 값은 aba 라는 문자열이 접두사/접미사로 a 한개가 일치함을 의미하는 것이다.
여기에서 idx를 1로 설정하면, b가 해당 idx로 변경되며, 앞에 부분의 매칭은 생략이 가능해진다.
(솔직히 확실히 와닿지는 않아서 이런식으로 작동한다는 개념을 받아들이는 느낌이다. 나중에 더 이해가 잘 되면 설명을 수정하러 와야겠다..)
다시 문자열 매칭을 시작한다. for문은 text만을 계속 반복하고 있기 때문에 이번에는 text[4]부터 시작해 매칭을 시도하게 된다.
두번째 불일치는 idx 가 5인 상황에서 발생한다.
이때도 table[5-1] = table[4] = 1이므로
1이라는 값은 aba 라는 문자열이 접두사/접미사로 a 한개가 일치함을 의미하며,
여기에서 idx를 1로 설정하면, b가 해당 idx로 변경되며, 앞에 부분의 매칭은 생략이 가능해진다.
다시 문자열 매칭을 또 시작하고, idx가 7까지 간다.
idx가 m-1 (문자열 길이 -1) 이 되는 순간 문자열을 발견한것이므로 탐색이 종료된다.
완벽하게 이해된것은 아니지만 작동 방식을 머리로 이해하는데엔 충분했던것 같다
좀더 이해가 되면 정리를 더 잘할 수 있도록 노력해야겠다.
✅ 한번에 볼수 있게 최종 버전 첨부
아래는 내가 참고한 블로그에 적혀있는 KMP 코드이다.
static void KMP(String parent, String pattern) {
int[] table = makeTable(pattern);
int n1 = parent.length();
int n2 = pattern.length();
int idx = 0; // 현재 대응되는 글자 수
for(int i=0; i< n1; i++) {
// idx번 글자와 짚더미의 해당 글자가 불일치할 경우,
// 현재 대응된 글자의 수를 table[idx-1]번으로 줄인다.
while(idx>0 && parent.charAt(i) != pattern.charAt(idx)) {
idx = table[idx-1];
}
// 글자가 대응될 경우
if(parent.charAt(i) == pattern.charAt(idx)) {
if(idx == n2-1) {
System.out.println(i-idx+1 + "번째에서 찾았습니다. ~" + (i+1) );
idx =table[idx];
}else {
idx += 1;
}
}
}
}
references
https://loosie.tistory.com/192
'알고리즘' 카테고리의 다른 글
[문자열 매칭] 보이어무어(Boyer-Moore) - Good Suffix Heuristics (0) | 2023.06.03 |
---|---|
[문자열 매칭] 보이어무어(Boyer-Moore) - Bad Character Heuristic (0) | 2023.06.02 |
[Python] 파이썬 코딩테스트대비용 복습 모음 (0) | 2023.04.15 |
[DP] 냅색 알고리즘 (0) | 2023.04.09 |
[기록용] 서브쿼리 이용하기 (MySQL) (0) | 2023.02.11 |