題干：

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).

Input

The first line is non-empty string?s, consisting of no more than?105?lowercase Latin letters and characters "?". The second line is non-empty string?p, consisting of no more than?105?lowercase Latin letters. Please note that the length of the string?pcan exceed the length of the string?s.

Output

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.

Examples

Input

bb??x??? aab

Output

2

Input

ab?c acb

Output

2

Note

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").

題目大意：

首先告訴你了兩個定義：1.字符串的異構（其實就是當前串的某個排列），2.子字符串，3.good string。

給你兩個字符串，如果s的子字符串中有和p的某個排列完全相同的，就可以說這個子字符串是符合條件的。S字符串有小寫字母和 ' ? ' 組成，而 ' ? ' 可以替換為任意的字母。最后問你，有多少個符合條件的子字符串。（子字符串是連續的若干個字符）

解題報告：

這種字符串涉及排列的，，顯然要計數一下的。因為包含p字符串中的所有字母及對應個數相同的話，那么就可以滿足。類似這道題【CodeForces - 1038A 】Equality （思維水題，預處理字符串）。

實現的話滑窗法就好了呀，用一個長度為len2的窗口，從頭滑到尾，順便維護字符出現的個數和ans就好。

AC代碼：

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int MAX = 1e5 +5; int bk[555],cnt[555],ans; char s[MAX],p[MAX]; int main() {cin>>(s+1);cin>>(p+1); // printf("%d",'?');int len1 = strlen(s+1);int len2 = strlen(p+1);if(len2 > len1) {puts("0");return 0;}for(int i = 1; i<=len2; i++) bk[p[i]]++;int l = 1,r = len2;for(int i = l; i<=r-1; i++) cnt[s[i]]++;while(r <= len1) {cnt[s[l-1]]--;cnt[s[r]]++;int rest = 0,flag = 1;for(int i = 'a'; i<='z'; i++) {if(cnt[i] > bk[i] ) {flag = 0;break;}if(cnt[i] < bk[i] ) rest += bk[i] - cnt[i];}if(flag && rest == cnt['?']) ans++;l++,r++;}printf("%d\n",ans);return 0 ; }

總結：注意為了統一形式，while上面那個for只能處理到r-1，然后相當于l=1，r=len2再開始處理，不然就得特判一下。。

總結

以上是生活随笔為你收集整理的【CodeForces - 144C】Anagram Search（尺取，滑窗问题，处理字符串计数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。