일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Redis
- 자바
- 스프링
- pandas
- 문자열
- docker
- 파이썬
- equals
- dfs
- springboot
- 헥사고날 아키텍처
- 위상정렬
- 포트앤어댑터 아키텍처
- dataframe
- spring security
- BFS
- series
- DP
- 이펙티브 자바
- 다익스트라
- ddd
- 백준
- JPA
- 세그먼트 트리
- 알고리즘
- 비트마스크
- 데이터 flow
- disjoint set
- UML
- java
- Today
- Total
코딩못하는사람
KMP 알고리즘(문자열 찾기) 본문
KMP 알고리즘이란?
우리가 문서에서 컨트롤+F눌러서 문자를 검색하던 항상 쓰였던 알고리즘이다.
알고리즘을 어떻게 구현하였을지 단순히 생각해보면 당연히 모든 인덱스에서 한번씩 패턴을돌려보는
N이 텍스트의 길이,M이 패턴의 길이라고 할 때 O(N*M)을 생각할 것이다.
하지만 KMP알고리즘은 O(N+M)정도로 줄여준다
KMP알고리즘에는 두가지 함수가 필요하다
전처리 테이블
KMP알고리즘은 접두사와 접미사를 기반으로 만드는 전처리 테이블이 필요하다
접두사와 접미사 같을때의 최대길이를
저장해주는 것이다
코드로 구현하면 다음과 같다.
KMP 함수구현
이렇게 전처리 테이블을 만들면 이제 테이블을 활용하여 겹치는 부분들을 활용하여 j는 순서대로 돌지만 i를 테이블값에 따라 빙빙 돌리면 된다
그림으로 보면
3번 인덱스에서 i와 j값이 틀렸다.
그러면 패턴에서 돌고있는 변수 i에 대해서 i-1값의 테이블값 인덱스를 찾아간다. table[2]의 값은 aba이므로 1일 것이다.
1의 인덱스는 b이므로 현재 j값 b와 같다.
i은 1부터 돌고 j는 변함없이 돈다.
위 과정들은 사실 table만들 때와 비슷하다. i를 계속 괴롭혀주면된다.
다르게 나온곳 인덱스-1 의 테이블값에 들어가서
겹쳤던 부분들과 비교하며 추적해 가는 과정이다.
i=table[i-1]로 text[j]와 pattern[i]가 같을때까지 반복될것이다
다음과 같이 패턴 인덱스가 끝까지왔는데 모두 일치했다?
그럼 그때의 인덱스 j에서 패턴의 길이를 빼주고 1을 더해주면 일치하는 부분을 찾았을 때의 인덱스를 얻을 수 있다.
이 때는 찾을 것을 찾은것이지 값이 다른게 아니므로 i=table[i]로 바꿔줘야된다고 생각할 수 있다.table[7]=3이므로 3
(abacaaba가 성공했다고 맨뒤로 넘기면 뒤에서 3번째 aba부터 다시 시작되서 생기는 값을 놓칠수있다)
이 코드는 밑에 문제에 KMP함수 부분이다
1786 찾기
1.접근
KMP알고리즘으로 답을 찾을때마다 정답 배열에 넣어준다
2.코드
3.배운점
- 이해하기 정말 힘든 알고리즘이였다.i값을 계속 돌리는게 어렵다
- table만드는 것과 kmp돌리는 함수가 만드는게 비슷하다는 걸 기억하자
출처: https://bowbowbow.tistory.com/6 [멍멍멍]
'알고리즘 정리' 카테고리의 다른 글
위상정렬 (Topological Sort),2252 줄세우기 (0) | 2020.09.27 |
---|---|
자료구조 트라이( 백준 5052 전화번호 목록) (1) | 2020.09.18 |
CCW 알고리즘 (선분 교차 판별) (1) | 2020.09.09 |
플로이드-와샬 알고리즘(11404 플로이드) (0) | 2020.09.03 |
벨만-포드 알고리즘(11657 타임머신) (1) | 2020.09.02 |