#P17835. [Ontak2022]STR

[Ontak2022]STR

题目描述

两个字符串 a,ba,b 相似,当且仅当它们长度相同,且对任意两个位置 i,ji,j 都有

ai=aj  ⟺  bi=bj.a_i=a_j\iff b_i=b_j.

也就是说,可以对 aa 中出现的字符做一次一致且一一对应的重命名,得到 bb。

给定文本串 tt 和模式串 pp,求 tt 中与 pp 相似的连续子串个数。按起始位置分别计数,允许不同出现重叠。

输入格式

第一行字符串 tt,第二行字符串 pp。

输出格式

输出相似子串数量。

数据范围

1≤∣t∣,∣p∣≤1061\le |t|,|p|\le10^6。

原题没有另列字符集范围。随附 C++ 程序按通常竞赛输入中的非空白单字节字符处理,使用256大小的字符表,不额外假定只有小写字母。

子任务

子任务 附加限制 分值
1 t=p 8
2 |t|≤100 5
3 |t|≤2000 12
4 无额外限制 75

样例 1

输入:

abababbab
pqp

输出:

5