该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

【题目描述】

给定一个字符串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 <= K <= LS – LT + 1, 那么S[K…K+LT-1]是S的一个子串， 如果该子串S[K…K+LT-1]是字符串T的同构串，那么ans增加1。你的任务就是输出ans最后的值。

输入格式

【输入格式】c.in

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

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

输出格式

【输出格式】c.out

一个整数，ans最后的值。

数据规模

【数据规模】

对于40%的数据，T 的长度不超过100，且S的长度不超过10000。

对于70%的数据，S的长度不超过1000000。

输入样例 c.in

输出样例 c.out

样例解释

aba

baababac

4

当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的同构串。