KMP
-
[백준] 1786번 찾기 (by Python)Programming/Algorithm 2021. 3. 24. 17:57
문제 https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net 풀이 parent string에 pattern string이 포함되어 있는지 찾을 수 있는 KMP 알고리즘에 대한 문제이다. KMP 알고리즘은 다음과 같다. 먼저, pattern과 같은 길이의 table array를 만들어준다. 이 때 pattern에서 prefix와 같은 내용의 postfix가 있다고 가정할 때, table의 원소는 같은 index를 가진 character가 postf..