题目描述

给定源串$S$和模式串$T$，问$S$中有多少子串和$T$匹配，这里，两个字符串$s$和$s’$匹配指，它们长度相同，且最多有$k$个位置字符不同。

输入格式

第一行输入一个字符串$S$； 第二行输入一个字符串$T$； 第三行输入一个整数$k$。

输出格式

输出一行一个整数，表示你的答案。

样例输入 #1

aabbaabb
aaba
1

样例输出 #1

3

说明/提示

有$1\leq |S|,|T|\leq 10^6,0\leq k\leq 5$。