KMP (2) 썸네일형 리스트형 [백준] 1786번: 찾기 - JAVA 🔗 문제 링크 BOJ 1786번: 찾기 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 📝 풀이 과정 주어진 문자열(T)에서 패턴 문자열(P)를 찾아 인덱스를 구하면 되는 간단한 문제이다. 하지만, 범위가 각각 $1,000,000 = 10^6$이므로 단순하게 문자열을 찾는 이중반복문으로 문제를 해결하려고 하면 $O(NM) = 10^{12}$으로 시간초과가 발생하게 된다. 따라서, 효율적으로 문자열을 찾는 알고리즘인 KMP 알고리즘을 사용해야 한다. 처음 문제를 풀 때, 기존 KMP에서 인덱스를 저장하는 .. [문자열 검색] KMP 알고리즘 단순하게 문자열을 찾는 방법을 생각해 보면 한 칸씩 비교해가며 일치하는지 확인하는 방법이 있다. ABABABC에서 ABAB가 몇 번 들어가는지 확인하는 예시이다. ⇒ 일치 ⇒ 불일치 ⇒ 일치 ⇒ 불일치 위와 같은 방식으로 찾게 되면 전체 문자열(len = N)에서 찾고자 하는 문자열(len = M)을 하나씩 비교해야 하므로 $O(NM)$의 시간복잡도를 갖게되어 비효율적인 알고리즘이 된다. 하지만, KMP 알고리즘을 사용하게 되면 시간복잡도가 $O(N+M)$으로 획기적으로 줄어들게 된다. 먼저 KMP 알고리즘을 배우기 전에 접두사와 접미사의 개념에 대해 알아야 한다. 예를 들어, apple의 접두사(prefix)는 a ap app appl apple 접미사(subfix)는 e le ple pple appl.. 이전 1 다음
