← 返回题目列表

AtCoder · abc307_h

Ex. 字幕

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

分数: 600 点

问题陈述

有一个长度 L 字符串 S 由大小写英文字母组成,显示在电子公告板上,宽度为 W。字符串 S 从右向左滚动,每次滚动一个字符的宽度。

显示屏重复以下循环: L+W-1 状态,第一个字符为 当最后一个字符时,从右边缘出现 S 当最后一个字符从右边缘出现时 S 从左边缘消失。

例如,当 W=5 和 S= ABC,板子循环显示以下七种状态:

  • ABC..
  • BC...
  • C....
  • ....A
  • ...AB
  • ..ABC
  • .ABC.

(. 表示不显示字符的位置。)

更准确地说,有不同的状态 k=0,\ldots,L+W-2 其中显示如下。

  • 让 f(x) 为余数 x 除以 L+W-1。的 (i+1)棋盘左侧第一个位置显示 (f(i+k)+1)- 第一个字符 S 当 f(i+k)<L,除此之外别无其他。

给你一个长度 W 字符串 P 由大写英文字母、小写英文字母组成, .,和 _.
查找其中的状态数 L+W-1 板的状态一致 P 除了具有 _.
更准确地说,找到满足以下条件的状态数。

  • 对于每个 i=1,\ldots,W,以下其中一项成立。
    • 的 i- 第一个字符 P is _.
    • 显示在 i从棋盘左边算起的第一个位置等于 i- 第一个字符 P.
    • 屏幕上不显示任何内容 i从棋盘左侧算起的第一个位置,以及 i- 第一个字符 P is ..

约束

  • 1 \leq L \leq W \leq 3\times 10^5
  • L 和 W 是整数。
  • S 是一个长度为 L 由大小写英文字母组成。
  • P 是一个长度为 W 由大小写英文字母组成, .,和 _.

输入

输入由标准输入按以下格式给出:

L W
S
P

输出

打印答案。


示例输入 1

3 5
ABC
..___

示例输出 1

3

共有三种所需状态,其中板显示 ....A, ...AB, ..ABC.


示例输入 2

11 15
abracadabra
__.._________ab

示例输出 2

2

示例输入 3

20 30
abaababbbabaabababba
__a____b_____a________________

示例输出 3

2

示例输入 4

1 1
a
_

示例输出 4

1