34720번 - 유사 단어 찾기 2

문제

주원이는 고대 언어 학계의 아이돌이다. 어느 날, 주원이는 자신과 같은 고대 언어 연구자인 선재가 고대 단어 $T$의 원본 단어를 찾는 작업에 착수했다는 소식을 들었다. 주원이 역시 $T$를 연구하고 있었기 때문에, 주원이는 조급함을 느꼈다.

주원이는 고고학자 정휘에게 달려가 자신에게도 유물을 달라고 부탁했다. 정휘는 주원이에게 $T$의 원본 단어가 포함되어 있는 문장 $S$가 새겨진 유물을 하나 제공해주었다.

주원이는 문장 $S$ 안의 비어 있지 않은 모든 연속된 부분 문자열을 원본 단어의 후보로 간주하기로 했다. 고대 언어에서는 글자 배열이 같더라도 문장 속 위치에 따라 의미가 달라질 수 있다. 따라서 문장 안에 같은 형태의 단어가 여러 번 등장하더라도, 그 위치가 다르면 서로 다른 후보로 취급한다.

$S$의 길이가 매우 길었기 때문에, 주원이는 가능한 후보들 중 $T$와의 유사도가 $K$ 이하인 후보들만 확인하기로 결정했다.

어떤 두 단어의 유사도란 한 단어를 다른 단어로 바꾸기 위해 필요한 최소 연산 횟수로 정의한다.

사용할 수 있는 연산은 다음과 같다.

• 추가: 현재 단어의 임의의 위치에 글자를 하나 추가한다.
• 제거: 현재 단어에서 임의의 글자를 하나 제거한다. 제거하면 남은 부분은 그대로 이어 붙는다.
• 변환: 현재 단어의 임의의 글자를 다른 글자로 바꾼다.

주원이는 각 0ドル \le i \le K$에 대해, 후보들 중 $T$와의 유사도가 정확히 $i$인 경우가 몇 개나 되는지 궁금해졌다. 그는 이 문제를 해결할 알고리즘을 순식간에 떠올렸지만, 학계의 아이돌 주원이는 너무나 바빴기 때문에 조수인 당신에게 이 작업을 대신 맡겼다.

최대한 빨리 작업을 끝내지 못하면, 주원이가 분노하여 월급을 주지 않을지도 모른다. $S,ドル $T,ドル $K$가 주어졌을 때, 정답을 계산하는 프로그램을 작성하라!

입력

첫 번째 줄에 $S$의 길이 $N$과 $T$의 길이 $M,ドル 정수 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 문장 $S$가 주어진다.

세 번째 줄에 단어 $T$가 주어진다.

출력

$K+1$개의 줄에 걸쳐, 정답을 출력한다. $i$번째 줄에는 유사도가 정확히 $i-1$인 후보의 개수를 출력한다.

제한

• 1ドル \le N \le 100,000円$
• 1ドル \le M \le 1000$
• 0ドル \le K \le \min(20, M)$
• $S,ドル $T$는 알파벳 소문자로만 구성된 문자열

노트