기록

문제 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m번 문자가 차례로 � www.acmicpc.net 풀이 1) 실패 함수 PI PI는 패턴에서 건너뛸 수 있는 문자의 개수를 의미하며 다음과 같이 구할 수 있다. ABAA의 PI = 1 접두사 접미사 접두사==접미사 1(문자의 개수) A A True 2(문자의 개수) AB AA False 3(문자의 개수) ABA BAA False A, AB, ABA, ABAA에 대해 위와 같은 방법으로 PI값을 구하면, [0, 0, 1, 1]이라는 배열을 얻을 수 있다. (인덱스 0은 0으로 연산) 위처럼 하나씩 ..