27525번 - 듣기 평가 연습

때는 먼 훗날, 알고리즘의 중요성이 많은 사람에게 알려지면서 SUAPC에 참가하고자 하는 사람 역시 늘어나게 되었다. 이러한 시대의 흐름에 발맞춰 SUAPC에도 듣기 평가 영역이 신설되었다. 래오는 코딩은 할 줄 알지만 듣기는 잘 못하기 때문에 기출 문제를 통해 듣기 평가를 연습하려 한다.

래오의 단어장은 길이 $N$의 문자열 $S$로, 기출 문제집은 길이 $M$의 문자열 $T$로 주어진다. 래오는 다음과 같은 형식의 연습 문제를 $Q$번 풀어야 한다. 두 문자열의 정확히 앞 $k$ 글자가 서로 같은 경우 두 문자열을 $k$-유사한 관계라 하자. 두 문자열 중 하나의 길이가 $k$ 미만이거나 두 문자열의 앞 $k+1$글자 이상이 서로 같을 경우 두 문자열은 $k$-유사하지 않다.

• $i$ $j$ $k$ : $T$의 부분 문자열 $T_i T_{i+1} ... T_j$와 $k$-유사한 $S$의 부분 문자열의 개수를 출력한다.

부분 문자열이란, 문자열의 연속된 일부를 말한다. 부분 문자열은 빈 문자열일 수 없다.

래오는 연습 문제를 매번 푸는 것에 지쳐 이를 자동으로 풀어 주는 프로그램을 만들려 한다. 래오를 도와 연습 문제에 대한 답을 출력하는 프로그램을 만들어 보자!

첫째 줄에 단어장의 길이 $N$, 기출 문제집의 길이 $M$, 연습 문제의 개수 $Q$가 공백으로 구분되어 주어진다. ($1 \leq N, M, Q \leq 100\,000$)

둘째 줄에 알파벳 소문자로 이루어진 길이 $N$의 문자열 $S$가 주어진다.

셋째 줄에 알파벳 소문자로 이루어진 길이 $M$의 문자열 $T$가 주어진다.

이후 $Q$개의 줄에 걸쳐 연습 문제가 i j k 와 같은 형태로 주어진다. ($1 \leq i \leq j \leq M ; 0 \leq k \leq M$)

각 연습 문제에 대한 답을 한 줄에 하나씩 순서대로 출력한다.