문제 링크 : https://www.acmicpc.net/problem/19265 문제 풀이 이 문제는 배열 p에 존재한 모든 $p_i$에 대해서 $T_i = Tp_i $ 인지를 S의 모든 구간에 T에 대해서 확인하는 문제이다. 여기서 어떤 형태를 비교하는 거니까 문자열 매칭과 비슷한 느낌을 받을 수 있다. 먼저 생각난 것은 KMP 였지만 KMP로는 풀 수 없는 형태였다. 실패함수가 좋은 형태로 나타나지 않기 때문에 KMP는 포기할 수 밖에 없었다. 이 상태에서 문제를 푸는 사고의 흐름이었다면 라빈-카프 해싱을 생각을 했어야 했다. $T_i = Tp_i $ 라는 것은 i 기반 해싱값과 pi 기반 해싱값이 같다는 거고, 좀 만 더 생각하고 식을 변형 시켜 보면 $\sum_{i}^{} i\times T_i ..