Score : $600$ points

问题描述

存在一个长度为 $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)<L$，则显示 $S$ 的第 $(f(i+k)+1)$ 个字符；否则不显示任何内容。

给你一个长度为 $W$ 的字符串 $P$，它由大写英文字母、小写英文字母、. 和 _ 组成。
找出在公告板的 $L+W-1$ 个状态中，除去 _ 位置外与 $P$ 相匹配的状态数目。
更精确地说，计算满足以下条件的状态数量。

• 对于 $i=1,\ldots,W$，满足以下任一条件：
  • 字符串 $P$ 的第 $i$ 个字符是 _。
  • 公告板左侧第 $i$ 个位置显示的字符等于字符串 $P$ 的第 $i$ 个字符。
  • 公告板左侧第 $i$ 个位置没有显示任何内容，并且字符串 $P$ 的第 $i$ 个字符是 .。

以上为通义千问 qwen-max 翻译，仅供参考。

Problem Statement

There is a length $L$ string $S$ consisting of uppercase and lowercase English letters displayed on an electronic bulletin board with a width of $W$. The string $S$ scrolls from right to left by a width of one character at a time.

The display repeats a cycle of $L+W-1$ states, with the first character of $S$ appearing from the right edge when the last character of $S$ disappears from the left edge.

For example, when $W=5$ and $S=$ ABC, the board displays the following seven states in a loop:

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

(. represents a position where no character is displayed.)

More precisely, there are distinct states for $k=0,\ldots,L+W-2$ in which the display is as follows.

• Let $f(x)$ be the remainder when $x$ is divided by $L+W-1$. The $(i+1)$-th position from the left of the board displays the $(f(i+k)+1)$-th character of $S$ when $f(i+k)<L$, and nothing otherwise.

You are given a length $W$ string $P$ consisting of uppercase English letters, lowercase English letters, ., and _.
Find the number of states among the $L+W-1$ states of the board that coincide $P$ except for the positions with _.
More precisely, find the number of states that satisfy the following condition.

• For every $i=1,\ldots,W$, one of the following holds.
  • The $i$-th character of $P$ is _.
  • The character displayed at the $i$-th position from the left of the board is equal to the $i$-th character of $P$.
  • Nothing is displayed at the $i$-th position from the left of the board, and the $i$-th character of $P$ is ..

Constraints

• $1 \leq L \leq W \leq 3\times 10^5$
• $L$ and $W$ are integers.
• $S$ is a string of length $L$ consisting of uppercase and lowercase English letters.
• $P$ is a string of length $W$ consisting of uppercase and lowercase English letters, ., and _.

Input

The input is given from Standard Input in the following format:

$L$ $W$

$S$

$P$

Output

Print the answer.

Sample Input 1

3 5
ABC
..___

Sample Output 1

3

There are three desired states, where the board displays ....A, ...AB, ..ABC.

Sample Input 2

11 15
abracadabra
__.._________ab

Sample Output 2

2

Sample Input 3

20 30
abaababbbabaabababba
__a____b_____a________________

Sample Output 3

2

Sample Input 4

1 1
a
_

Sample Output 4

1

update @ 2024/3/10 08:43:09