34837번 - 문자열 일치도

문제

길이가 같은 두 문자열의 일치도를 두 문자열이 같은 문자를 가지는 위치의 수라고 하자.

영어 알파벳 소문자로만 이루어진 두 문자열 $S$와 $T$가 주어진다. $S$와 $T$의 길이는 각각 $N$과 $M$이다. $N$은 $M$보다 크거나 같다.

$S$의 모든 길이가 $M$인 부분 문자열 $N-M+1$개에 대해 $T$와의 일치도의 합을 구하여라.

부분 문자열의 정의는 노트를 참고하라.

입력

첫째 줄에 문자열 $S$의 길이 $N$과 문자열 $T$의 길이 $M$이 공백으로 구분되어 주어진다. (1ドル \leq M \leq N \leq 200,000円$)

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

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

출력

첫째 줄에 $S$의 모든 길이가 $M$인 부분 문자열 $N-M+1$개에 대해 $T$와의 일치도의 합을 출력한다.

제한

노트

부분 문자열이란, 문자열에서 연속한 부분에 해당하는 문자열이다. 예를 들어 ab, bca, abca는 abca의 부분 문자열이고, ac, ba는 abca의 부분 문자열이 아니다.