3567. 周期字符串

单测试点时限: 5.0 秒

内存限制: 512 MB

有两个无限长的字符串 , ,周期分别为 ,

周期的定义如下:字符串 的周期为 ,则字符串 满足 , 对于 。其中 表示 从第 个字符到第 个字符的子串。

现求满足 的个数。亦即,两个字符串前 个位置有多少位置是相等的?

输入

第一行三个整数 ()。

第二行,长度为 的字符串

第三行,长度为 的字符串

, 均由 AGCT 组成。

样例

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

10 人解决,109 已尝试。

13 份提交通过,共有 631 份提交。

8.9 EMB 奖励。

创建: 6 月,1 周前.

修改: 6 月,1 周前.

最后提交: 2 月,2 周前.

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

标签
fft