跑马灯

题目描述

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

当 $S$ 的最后一个字符从左侧边缘消失时,$S$ 的第一个字符从右侧边缘出现,显示以 $L+W-1$ 个状态为一个周期循环。

例如,当 $W=5$、$S=$ ABC 时,公告板循环显示以下 7 个状态:

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

这里 . 表示没有字符显示的位置。

更准确地说,对于 $k=0,\ldots,L+W-2$,存在互不相同的状态,其显示如下。

设 $f(x)$ 为 $x$ 除以 $L+W-1$ 所得的余数。公告板上从左边数第 $(i+1)$ 个位置,当 $f(i+k)\lt L$ 时显示 $S$ 的第 $(f(i+k)+1)$ 个字符,否则不显示任何内容。

给定一个长度为 $W$ 的、由大小写英文字母、. 和 _ 组成的字符串 $P$。

求公告板的 $L+W-1$ 个状态中,与 $P$ 在除 _ 以外的所有位置上完全一致的状态数量。

更准确地说,求满足以下条件的状态数量:

对于每个 $i=1,\ldots,W$,以下条件之一成立。

• $P$ 的第 $i$ 个字符是 _。
• 公告板第 $i$ 个位置显示的字符与 $P$ 的第 $i$ 个字符相同。
• 公告板第 $i$ 个位置什么都没有显示,且 $P$ 的第 $i$ 个字符是 .。

输入格式

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

$L$ $W$
$S$
$P$

输出格式

输出答案。

样例

3 5
ABC
..___

3

共有三种满足条件的状态,分别显示 ....A、...AB、..ABC。

11 15
abracadabra
__.._________ab

2

20 30
abaababbbabaabababba
__a____b_____a________________

2

1 1
a
_

1

数据范围

• $1 \le L \le W \le 3\times 10^5$
• $L$ 和 $W$ 是整数
• $S$ 是由大小写英文字母组成的长度为 $L$ 的字符串
• $P$ 是由大小写英文字母、. 和 _ 组成的长度为 $W$ 的字符串