暂无测试数据。

题目描述

给定一个字符串 \(T\)，它的长度是 \(LT\)，
那么字符串 \(T\) 可以用字符数组 T[1..LT] 来表示。

你可以把 \(T\) 的任意两个字符交换位置，
你可以交换任意多次。
经过交换之后的字符串被称为 \(T\) 的同构串。

例如：
T="abac"
那么 "aabc"、  "aacb"、 "baac"、 "baca"、 "bcaa"、 "caab"、 "caba"、 "cbaa"等都是字符串T的同构串。

而"baab"、 "bcab"等都不是字符串 \(T\) 的同构串。

再给定一个字符串 \(S\)，长度是 \(LS\)，
那么字符串 \(S\) 可以用字符数组 S[1..LS] 来表示。
初始时，ans=0 。
对于每一个下标 \(K\)，其中 \(1 \leq K \leq LS–LT+1\), 
那么 S[K…K+LT-1] 是 \(S\) 的一个子串，
如果该子串 S[K…K+LT-1] 是字符串 \(T\) 的同构串，
那么 ans 增加 1。
你的任务就是输出 ans 最后的值。

输入

第一行，一个字符串 \(T\)。
长度不超过10000，
\(T\) 的每个字符要么是小写字母要么是大写字母。

第二行，一个字符串 \(S\)。
长度是5000000，
\(S\) 的每个字符要么是小写字母要么是大写字母。

输出

一个整数，\(ans\) 最后的值。

样例输入

aba
baababac

样例输出

4

数据范围限制

对于 \(40\%\) 的数据，\(T\) 的长度不超过100，且 \(S\) 的长度不超过10000。
对于 \(70\%\) 的数据，\(S\) 的长度不超过1000000。

提示

当 K=1时，S[1..3] = "baa"，是T的同构串。
当 K=2时，S[2..4] = "aab"，是T的同构串。
当 K=3时，S[3..5] = "aba"，是T的同构串。
当 K=4时，S[4..6] = "bab"，不是T的同构串。
当 K=5时，S[5..7] = "aba"，是T的同构串。
当 K=6时，S[6..8] = "bac"，不是T的同构串。

来源

基础篇练习2.3