암호 찾기

시간 제한1초메모리 제한256 MB

요약

길이가 N인 두 숫자 문자열 A와 B, 그리고 정수 K가 주어질 때, A와 B 모두의 부분 문자열이면서 길이가 K인 서로 다른 문자열의 개수를 구한다.

문제

오랫동안 세계 4대 문명이 최초의 문명으로 알려져 있었지만, 최근 이를 뒤집는 고고학적 연구 결과가 발표되었습니다. 새로 발견된 ‘폴리매스 문명’은 기원전 9000년경부터 존재했음이 확인되었습니다.

당신은 고고학자로서 폴리매스 문명을 연구하는 임무를 맡고 있습니다. 폴리매스 문명은 보안을 위해 특이한 형식의 비밀번호를 사용했는데, 그 규칙은 다음과 같습니다.

사람들은 비밀번호 규칙과 관련된 숫자 두 개로 이루어진 문자열을 만들었습니다. 두 문자열 $A$ 와 $B$ 의 길이는 각각 $N$ 으로 같습니다. $A$ 와 $B$ 모두의 부분 문자열이면서 길이가 정확히 $K$ 인 문자열이 비밀번호가 됩니다.

비밀번호가 여러 개이거나 하나도 없을 수도 있는데, 이런 경우에는 $A$ 와 $B$ 의 기록이 잘못된 것입니다. 기록이 올바른지 판정하기 위해, 가능한 서로 다른 비밀번호의 수를 구하는 프로그램을 작성하세요.

첫 줄에는 각 문자열의 길이 $N$ 과 뽑아낼 수의 자릿수 $K$ 가 주어집니다. 둘째 줄에는 문자열 $A$ 가 주어집니다. 셋째 줄에는 문자열 $B$ 가 주어집니다.

$A$ 와 $B$ 모두의 부분 문자열이고 길이가 $K$ 인 서로 다른 문자열의 수를 출력합니다.