当前没有测试数据。

题目描述

一条由 $n$ 个字符格组成的带子首尾相接，形成一个环。环上有一个固定的读数标记，它位于原第 $n$ 个格与原第 $1$ 个格之间。从标记出发顺时针读取一周，初始字符串为 $S$。

现在希望通过一次补片操作，使读数变为目标字符串 $T$。一次操作由两个整数 $(c,e)$ 确定，满足 $1 \le c \le h,\quad c < e \le n.$

操作过程如下:

1. 取下标记后顺时针的前 $c$ 个原格，即原第 $1$ 至第 $c$ 个格；
2. 选择一个小写英文字母，把取下的这 $c$ 个格全部涂成该字母；
3. 收拢余下的格子，再把涂好的整段插到原第 $e$ 个格之后。

若 $e = n$，第3步表示把涂好的整段插在原第 $n$ 个格与读数标记之间。

形式化地，设第 2 步选择的字母为 $a$，记 $a^c$ 为由 $c$ 个字符 $a$ 组成的字符串。操作后的读数为 $S_{c+1}S_{c+2}\cdots S_e\ a^c\ S_{e+1}S_{e+2}\cdots S_n.$

当 $e = n$ 时，最后一段为空串。字符串下标从 $1$ 开始。

只统计不同的参数对 $(c,e)$，不计算第 2 步选择的字母。求有多少个参数对能够使操作后的读数恰好等于 $T$。

输入格式

从文件 circle.in 中读取数据。

第一行包含两个整数 $n, h$。

第二行包含长度为 $n$ 的字符串 $S$。

第三行包含长度为 $n$ 的字符串 $T$。

输出格式

输出到文件 circle.out 中。

输出一个非负整数，表示合法参数对 $(c,e)$ 的数量。

样例

6 3
ababab
ababbb

2

样例解释

两个合法参数对为 $(2,5)$ 和 $(2,6)$。

• 选择 $(2,5)$ 时，保留在标记后的部分依次为 aba，把取下的两个格都涂成 b，再接上最后一个原格 b，得到 ababbb；
• 选择 $(2,6)$ 时，保留在标记后的部分为 abab，把取下的两个格都涂成 b 并插在标记前，同样得到 ababbb。

所有 $e<5$ 的操作都会把原第 $5$ 个格留在未重涂的后缀中，因此不可能得到目标读数；其余参数对也不能同时满足未重涂部分的字符要求。

数据规模与约定

• $2 \le n \le 3\times 10^5$；
• $1 \le h < n$；
• $S,T$ 均只包含小写英文字母，且长度均为 $n$；

各子任务为相互独立的测试组，得分为通过测试组的分值之和。

原题链接

原题链接