Anagram Search

题意翻译

若字符串 $s$ 在交换字母顺序后可以得到 $t$，则称两个串是“相似”的（$s$ 为 $t$ 的 anagram）。 给定由小写字母与“?”组成的字符串 $s$ 和由小写字母组成的字符串 $t$。定义一个字符串是好的，当且仅当这个串存在某种将每个“?”替换为一个小写字母的方式，使它与 $p$ 相似（是 $p$ 的 anagram）。问 $s$ 有多少子串是好的（两子串不同当且仅当它们在 $s$ 中的开始位置或终止位置不同）。 ### 输入格式 两行，每行一个字符串，分别为 $s,t$。 ### 输出格式 一行一个整数，代表 $s$ 的好的子串的数量。

题目描述

A string $ t $ is called an anagram of the string $ s $ , if it is possible to rearrange letters in $ t $ so that it is identical to the string $ s $ . For example, the string "aab" is an anagram of the string "aba" and the string "aaa" is not. The string $ t $ is called a substring of the string $ s $ if it can be read starting from some position in the string $ s $ . For example, the string "aba" has six substrings: "a", "b", "a", "ab", "ba", "aba". You are given a string $ s $ , consisting of lowercase Latin letters and characters "?". You are also given a string $ p $ , consisting of lowercase Latin letters only. Let's assume that a string is good if you can obtain an anagram of the string $ p $ from it, replacing the "?" characters by Latin letters. Each "?" can be replaced by exactly one character of the Latin alphabet. For example, if the string $ p $ = «aba», then the string "a??" is good, and the string «?bc» is not. Your task is to find the number of good substrings of the string $ s $ (identical substrings must be counted in the answer several times).

输入输出格式

输入格式

The first line is non-empty string $ s $ , consisting of no more than $ 10^{5} $ lowercase Latin letters and characters "?". The second line is non-empty string $ p $ , consisting of no more than $ 10^{5} $ lowercase Latin letters. Please note that the length of the string $ p $ can exceed the length of the string $ s $ .

输出格式

Print the single number representing the number of good substrings of string $ s $ . Two substrings are considered different in their positions of occurrence are different. Thus, if some string occurs several times, then it should be counted the same number of times.

输入输出样例

输入样例 #1

bb??x???
aab

输出样例 #1

2

输入样例 #2

ab?c
acb

输出样例 #2

2

说明

Consider the first sample test. Here the string $ s $ has two good substrings: "b??" (after we replace the question marks we get "baa"), "???" (after we replace the question marks we get "baa"). Let's consider the second sample test. Here the string $ s $ has two good substrings: "ab?" ("?" can be replaced by "c"), "b?c" ("?" can be replaced by "a").