← 返回题目列表

Codeforces · 144/C

C. 字谜搜索

中文机器翻译题面 查看原题

如果可以重新排列 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”代替)。