分数: 600 点
问题陈述
有一个长度 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)+1)- 第一个字符 S 当 f(i+k)<L,除此之外别无其他。
给你一个长度 W 字符串 P 由大写英文字母、小写英文字母组成, .,和 _.
查找其中的状态数 L+W-1 板的状态一致 P 除了具有 _.
更准确地说,找到满足以下条件的状态数。
- 对于每个 i=1,\ldots,W,以下其中一项成立。
- 的 i- 第一个字符 P is
_. - 显示在 i从棋盘左边算起的第一个位置等于 i- 第一个字符 P.
- 屏幕上不显示任何内容 i从棋盘左侧算起的第一个位置,以及 i- 第一个字符 P is
..
- 的 i- 第一个字符 P is
约束
- 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