알고리즘/백준(BOJ)
[백준/C++] 1786번 찾기 && kmp 알고리즘
https://www.acmicpc.net/problem/1786 1786번: 찾기 첫째 줄에, T 중간에 P가 몇 번 나타나는지를 나타내는 음이 아닌 정수를 출력한다. 둘째 줄에는 P가 나타나는 위치를 차례대로 공백으로 구분해 출력한다. 예컨대, T의 i～i+m-1번 문자와 P의 1～m www.acmicpc.net kmp 알고리즘에 관한 문제이다. kmp 알고리즘이란, 문자열 패턴 매칭을 O(nm)이 아닌, O(n+m)에 해결할 수 있도록 해주는 문제이다. 이 알고리즘을 이해하기 위해서는, 접두사 접미사의 개념과 pi라고 칭한 이동경로 테이블을 왜 만드는지에 대한 이해가 필요하다. 이동경로 table은, 패턴의 부분 문자열(길이 1~원래 길이까지)마다 접두,접미사가 최대로 겹치는 길이를 저장해둔 tab..
