AT_abc307_h [ABC307Ex] Marquee

题目描述

有一个长度为 $L$ 的字符串 $S$，由英文字母大写和小写字母组成，显示在宽度为 $W$ 的电子显示屏上。$S$ 会以每次向左滚动一个字符宽度的方式在显示屏上切换显示。

当 $S$ 的最后一个字符从左端消失的同时，$S$ 的第一个字符会从右端出现，整个过程以 $L+W-1$ 为周期重复。

例如，当 $W=5$，$S=$ ABC 时，显示屏的显示状态依次为：

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

共 $7$ 种状态不断循环显示。（其中 . 表示该位置没有字符显示）

更严格地说，对于每个 $k=0,\ldots,L+W-2$，定义如下不同的显示状态：

• 用 $f(x)$ 表示 $x$ 除以 $L+W-1$ 的余数。对于显示屏从左到右的第 $(i+1)$ 个位置，如果 $f(i+k)<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$

输出格式

输出一个整数，表示满足条件的状态数量。

输入输出样例 #1

输入 #1

3 5
ABC
..___

输出 #1

3

输入输出样例 #2

输入 #2

11 15
abracadabra
__.._________ab

输出 #2

2

输入输出样例 #3

输入 #3

20 30
abaababbbabaabababba
__a____b_____a________________

输出 #3

2

输入输出样例 #4

输入 #4

1 1
a
_

输出 #4

1

说明/提示

限制

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

样例解释 1

当显示屏显示为 ....A、...AB、..ABC 时，共有 $3$ 种状态符合条件。

由 ChatGPT 4.1 翻译