- Today
- Yesterday
- Total
메이쁘
(JAVA) 백준 1786번 : 찾기 --- [KMP] 본문
https://www.acmicpc.net/problem/1786
1786번: 찾기
첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 �
www.acmicpc.net
안녕하세요.
이 문제는 문자열 검색 알고리즘인 KMP의 기본 문제로서
문제에도 노골적으로 O(전체 문자열 길이 + 찾으려는 문자열 길이) 의 시간복잡도로 문자열을 탐색하라고 나와있다.
KMP 알고리즘에 대해 알고싶으면 백준 1701번 문제 포스팅을 보고 와도 좋다.
https://maivve.tistory.com/203
(JAVA) 백준 1701번 : Cubeditor
https://www.acmicpc.net/problem/1701 1701번: Cubeditor Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새..
maivve.tistory.com
요점만 말하면
1) 찾으려는 문자열의 접두사와 접미사 길이를 담은 배열 pi
2) 이 pi를 활용하여 전체 문자열에서 중복을 제거해가며 일치하는 문자열이 있는지 체크
3) 문자열의 시작 위치 인덱스를 리스트에 담는다.
가 KMP 알고리즘이고, 이 문제 풀이의 핵심이다.
자세한 설명은 위에 포스팅에 담겨있어서 여기서는 따로 개념 설명은 담지 않겠습니다.
이상입니다.
감사합니다!
소스코드
'Algorithm > Baekjoon' 카테고리의 다른 글
| (JAVA) 백준 1259번 : 팰린드롬수 --- [문자열] (0) | 2020.09.03 |
|---|---|
| (JAVA) 백준 1305번 : 광고 --- [KMP] (0) | 2020.09.03 |
| (JAVA) 백준 1701번 : Cubeditor --- [KMP] (0) | 2020.09.02 |
| (JAVA) 백준 13305번 : 주유소 (0) | 2020.09.01 |
| (JAVA) 백준 15904번 : UCPC는 무엇의 약자일까? (0) | 2020.08.31 |
