如果可以重新排列 t 中的字母以使其与字符串 s 相同,则字符串 t 称为字符串 s 的字谜词。例如,字符串“aab”是字符串“aba”的字谜词,而字符串“aaa”则不是。
如果可以从字符串 s 中的某个位置开始读取字符串 t,则该字符串 t 被称为字符串 s 的子字符串。例如,字符串“aba”有六个子字符串:“a”、“b”、“a”、“ab”、“ba”、“aba”。
给定一个字符串 s,由小写拉丁字母和字符“?”组成。您还会获得一个字符串 p,仅由小写拉丁字母组成。假设一个字符串是好的,如果你能从中获得字符串 p 的字谜词,替换“?”由拉丁字母组成的字符。每个 ”?”可以用拉丁字母表中的一个字符来替换。例如,如果字符串 p = «aba»,则字符串“a??”很好,而字符串 «?bc» 则不好。
你的任务是找出字符串 s 的好子串的数量(相同的子串必须在答案中计算多次)。
输入
第一行是非空字符串s,由不超过105个小写拉丁字母和字符“?”组成。第二行是非空字符串p,由不超过105个小写拉丁字母组成。请注意,字符串 p 的长度可以超过字符串 s 的长度。
输出
打印代表字符串 s 的好子串数量的单个数字。
两个子串被认为是不同的,因为它们出现的位置不同。因此,如果某个字符串出现多次,则应将其计数为相同的次数。
示例
输入 #1
bb??x??? aab
输出 #1
2
输入 #2
ab?c acb
输出 #2
2
注意
考虑第一个样本测试。这里字符串 s 有两个好的子字符串:“b??” (替换问号后,我们得到“baa”)、“???” (替换问号后,我们得到“baa”)。
让我们考虑第二个示例测试。这里字符串 s 有两个好的子字符串:“ab?” (“?”可以用“c”代替),“b?c”(“?”可以用“a”代替)。