/ 
Time Limit: 5 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
英大文字および英小文字からなる長さ L の文字列 S が幅 W の電光掲示板に表示されており、S が右から左へ 1 文字分の幅ずつスクロールするように切り替わっています。
表示は、S の最後の文字が左端から消えると同時に S の最初の文字が右端から現れる、L+W-1 周期での繰り返しとなっています。
例えば W=5、S= ABC のとき、電光掲示板の表示は
ABC..BC...C........A...AB..ABC.ABC.
の 7 つの状態を繰り返します。（. は文字が表示されていないことを表します）
より厳密には、各 k=0,\ldots,L+W-2 に対して、表示が次のようになっている相異なる状態が定まります。
- x を L+W-1 で割ったあまりを f(x) と表す。電光掲示板の左から (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 文字目は
.である
- 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 であるときの 3 状態が該当します。
入力例 2
11 15 abracadabra __.._________ab
出力例 2
2
入力例 3
20 30 abaababbbabaabababba __a____b_____a________________
出力例 3
2
入力例 4
1 1 a _
出力例 4
1
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
..
- 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