题目描述

给定一个字符串 \(s\)，可以把 \(s\) 的任意两个字符交换位置，也可以交换任意多次，经过交换之后的字符串被称为 \(s\) 的同构串。
例如 \(s=”abac”\)，则 \(”aabc”,”aacb”,”baac”\) 等都是 \(s\) 的同构串， 而 \(”baab”,”bcab”\) 等都不是 \(s\) 的同构串。
输入字符串 \(s\) 和 \(t\)，求 \(t\) 有多少个子串与 \(s\) 同构。

格式

输入格式

第一行为字符串 \(s\)，长度不超过 \(1000\)；第二行为字符串 \(t\)，长度不超过 \(5000000\)；所有输入只包含小写字母。

输出格式

仅一个整数，表示同构子串的个数。

样例1

样例输入1

aba
baababac

样例输出1

4

限制

\(40\%\) 数据中，\(s\) 串长不超过 \(200\)，\(t\) 串长不超过 \(100000\)；
\(100\%\) 数据中，\(s\) 串长不超过 \(1000\)，\(t\) 串长不超过 \(5000000\)。

来源

地址：芜湖市二十七中电脑班刷题课
作者：汪老师
模拟赛\(T4\)

文件IO

freopen("same.in","r",stdin);
freopen("same.out","w",stdout);