103077: [Atcoder]ABC307 Ex - Marquee

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

Score : $600$ points

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

Input

Output

分数:$600$分

问题描述

有一个宽度为$W$的电子公告板上显示着长度为$L$的字符串$S$,该字符串由大写和小写英文字母组成。字符串$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$的余数。当$f(i+k)<L$时,公告板从左侧的第$(i+1)$个位置显示$S$的第$(f(i+k)+1)$个字符,否则不显示任何字符。

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

找出公告板$L+W-1$个状态中与$P$除了位置上有_外完全一致的状态数。更确切地说,找出满足以下条件的状态数。

  • 对于$i=1,\ldots,W$中的每一个$i$,以下三个条件之一成立。
    • $P$的第$i$个字符为_
    • 公告板从左侧的第$i$个位置显示的字符等于$P$的第$i$个字符。
    • 公告板从左侧的第$i$个位置不显示任何字符,且$P$的第$i$个字符为.

限制条件

  • $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

加入题单

上一题 下一题 算法标签: