BOJ/KMP
-
[Python 3] 백준 1786-찾기BOJ/KMP 2020. 2. 17. 19:34
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 일치한다면, i를 출력하는 식이다. www.acmicpc.net KMP를 그대로 이용하는 문제. KMP 알고리즘 Knuth-Morris-Pratt 알고리즘의 줄임말이다. 입력으로 전체 문자열과 찾고 싶은 문자열을 받는다. 뇌를 비우고 문자열을 확인한다면, 첫 번째 문자부터 끝까지 다 뒤져 보면서 맞는 것을 찾을 수 있겠지만, 전체 문자열의 길이=N, 찾고 싶은 문자열의 길이=M이라 하면 O(NM)이다. 못 써먹는다. 다..