#P17835. [Ontak2022]STR
[Ontak2022]STR
题目描述
两个字符串 相似,当且仅当它们长度相同,且对任意两个位置 都有
也就是说,可以对 中出现的字符做一次一致且一一对应的重命名,得到 。
给定文本串 和模式串 ,求 中与 相似的连续子串个数。按起始位置分别计数,允许不同出现重叠。
输入格式
第一行字符串 ,第二行字符串 。
输出格式
输出相似子串数量。
数据范围
。
原题没有另列字符集范围。随附 C++ 程序按通常竞赛输入中的非空白单字节字符处理,使用256大小的字符表,不额外假定只有小写字母。
子任务
| 子任务 | 附加限制 | 分值 |
|---|---|---|
| 1 | t=p | 8 |
| 2 | |t|≤100 | 5 |
| 3 | |t|≤2000 | 12 |
| 4 | 无额外限制 | 75 |
样例 1
输入:
abababbab
pqp
输出:
5