34719번 - 유사 단어 찾기 1

문제

선재는 고대 언어를 연구하고 있다. 선재는 오랜 세월 전해 내려오는 기록에서 단어 $T$를 발견했다. 연구 끝에 선재는 $T$가 고대 언어의 어떤 원본 단어를 잘못 적은 것이며 원래 단어와의 유사도가 $K$ 이하라는 사실을 알아냈다.

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

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

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

그러던 중 고고학자 정휘가 유물을 발견했다. 유물에는 고대 언어로 된 문장 $S$가 써 있었다. 선재는 $T$의 원본 단어가 $S$에 포함되어 있다는 사실을 알게 되어 $S$를 조사하기로 했다.

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

모든 후보를 전부 조사하기에는 시간이 부족했기에 선재는 유사도가 낮은 후보부터 순서대로 분석하기로 했다. 작업을 시작하기에 앞서 선재는 각 0ドル \le i \le K$에 대해 유사도가 정확히 $i$인 후보가 몇 개나 되는지 조사하기로 했다.

그러나 선재는 너무나 멍청하여 이 문제를 해결하지 못했다. 그래서 여러분에게 도움을 요청했다. 불쌍한 선재를 위해, 문제를 해결해주자!

입력

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

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

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

출력

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

제한

• 1ドル \le N \le 5000$
• 1ドル \le M \le 1000$
• 0ドル \le K \le M$
• $S,ドル $T$는 알파벳 소문자로만 구성된 문자열

노트