3567. 周期字符串

单点时限: 5.0 sec

内存限制: 512 MB

有两个无限长的字符串 $s$, $t$,周期分别为 $n$, $m$:

周期的定义如下:字符串 $s$ 的周期为 $n$,则字符串 $s$ 满足 $s[1..n]=s[n+1..2n]=s[dn+1..(d+1)n]$, 对于 $d \ge 0$。其中 $s[i..j]$ 表示 $s$ 从第 $i$ 个字符到第 $j$ 个字符的子串。

现求满足 $1 \le i \le k$ 且 $s_i=t_i$ 的 $i$ 的个数。亦即,两个字符串前 $k$ 个位置有多少位置是相等的?

输入格式

第一行三个整数 $n, m, k$ ($1 \le n,m \le 125~512, 1 \le k \le 10^{18}$)。

第二行,长度为 $n$ 的字符串 $s$。

第三行,长度为 $m$ 的字符串 $t$。

$s$, $t$ 均由 AGCT 组成。

样例

Input
5 4 9
AGCAG
AGCC
Output
5
Input
5 4 9
AAAAA
AAAA
Output
9

11 人解决,117 人已尝试。

14 份提交通过,共有 809 份提交。

8.5 EMB 奖励。

创建: 2 年,6 月前.

修改: 2 年,6 月前.

最后提交: 6 天,22 小时前.

来源: 2018 华东师范大学校赛

题目标签
fft