← 返回题目列表

AtCoder · icpc2013summer_day3_h

H. 几乎相同的子串

中文机器翻译题面 查看原题

不幸的伊库塔有一串重要的字符。T是一个根据病毒而变化的字符串。 它已被重写为T'。那个病毒 已知T的一个字符被改写为不同的字符。即T和 在T'恰好有一个字符不同。伊库塔君 要恢复T, 出现T的文档S已准备好。 准备恢复T在S的子字符串中 我想找出可能匹配T的项目数。

文字列T'和文件S。 来自行 S = a1 a2 a3 ... a|S|长度|T'|的子字符串 与ak ak+1 ... ak+|T'|-1(1 \leq k \leq |S| - |T'| + 1) 变为T'进行比较,找出仅相差 1 个字符的字符数。

输入

输入按以下格式给出。

S
T'
  • 在第一行S。 来自行

  • 在第二行T'。 来自行

  • S, T'仅由大写和小写字母组成。

约束

输入中的每个变量都满足以下约束。

  • 1 \leq |S| \leq 300,000

  • 1 \leq |T'| \leq |S|

输出

输出一行中满足条件的子串数量。

示例输入 1

abcbcdbc
abc

样本输入 1 的输出 cbc 从

2
  • S的第三个字符开始, 从 S第6个字符开始的dbc满足条件。

示例输入 2

aaaaaa
aaaaaa

样本输入 2 的输出

0
  • 不得计算确切的字符串。

示例输入 3

baaaaaaaa
b

样本输入 3 的输出

8