310919: CF1909G. Pumping Lemma

G. Pumping Lemmatime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputTanchiky & Siromaru - Crystal Gravity⠀

You are given two strings $s$, $t$ of length $n$, $m$, respectively. Both strings consist of lowercase letters of the English alphabet.

Count the triples $(x, y, z)$ of strings such that the following conditions are true:

• $s = x+y+z$ (the symbol $+$ represents the concatenation);
• $t = x+\underbrace{ y+\dots+y }_{k \text{ times}} + z$ for some integer $k$.

Input

The first line contains two integers $n$ and $m$ ($1 \leq n < m \leq 10^7$) — the length of the strings $s$ and $t$, respectively.

The second line contains the string $s$ of length $n$, consisting of lowercase letters of the English alphabet.

The third line contains the string $t$ of length $m$, consisting of lowercase letters of the English alphabet.

Output

Output a single integer: the number of valid triples $(x, y, z)$.

ExamplesInput

4 8
abcd
abcbcbcd

Output

1

Input

3 5
aaa
aaaaa

Output

5

Input

12 16
abbababacaab
abbababababacaab

Output

8

Note

In the first test case, the only valid triple is $(x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"})$. In fact,

• $\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$;
• $\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$.

In the second test case, there are $5$ valid triples:

• $(x, y, z) = (\texttt{""}, \texttt{"a"}, \texttt{"aa"})$;
• $(x, y, z) = (\texttt{""}, \texttt{"aa"}, \texttt{"a"})$;
• $(x, y, z) = (\texttt{"a"}, \texttt{"a"}, \texttt{"a"})$;
• $(x, y, z) = (\texttt{"a"}, \texttt{"aa"}, \texttt{""})$;
• $(x, y, z) = (\texttt{"aa"}, \texttt{"a"}, \texttt{""})$.

In the third test case, there are $8$ valid triples:

• $(x, y, z) = (\texttt{"ab"}, \texttt{"ba"}, \texttt{"babacaab"})$;
• $(x, y, z) = (\texttt{"abb"}, \texttt{"ab"}, \texttt{"abacaab"})$;
• $(x, y, z) = (\texttt{"abba"}, \texttt{"ba"}, \texttt{"bacaab"})$;
• $(x, y, z) = (\texttt{"ab"}, \texttt{"baba"}, \texttt{"bacaab"})$;
• $(x, y, z) = (\texttt{"abbab"}, \texttt{"ab"}, \texttt{"acaab"})$;
• $(x, y, z) = (\texttt{"abb"}, \texttt{"abab"}, \texttt{"acaab"})$;
• $(x, y, z) = (\texttt{"abbaba"}, \texttt{"ba"}, \texttt{"caab"})$;
• $(x, y, z) = (\texttt{"abba"}, \texttt{"baba"}, \texttt{"caab"})$.

题目大意：

给定两个字符串 s 和 t，长度分别为 n 和 m。字符串由小写英文字母组成。计算满足以下条件的三元组 (x, y, z) 的数量：

1. s = x + y + z （+ 表示字符串连接）；
2. t = x + y + ... + y + z （y 重复 k 次，k 为某个整数）。

输入输出数据格式：

输入：
- 第一行包含两个整数 n 和 m（1 ≤ n < m ≤ 10^7），分别表示字符串 s 和 t 的长度。
- 第二行包含一个长度为 n 的字符串 s，由小写英文字母组成。
- 第三行包含一个长度为 m 的字符串 t，由小写英文字母组成。

输出：
- 输出一个整数：满足条件的三元组 (x, y, z) 的数量。

示例：

输入：
4 8
abcd
abcbcbcd

输出：
1

解释：
唯一有效的三元组是 (x, y, z) = ("a", "bc", "d")。实际上，
- "abcd" = "a" + "bc" + "d"；
- "abcbcbcd" = "a" + "bc" + "bc" + "bc" + "d"。题目大意： 给定两个字符串 s 和 t，长度分别为 n 和 m。字符串由小写英文字母组成。计算满足以下条件的三元组 (x, y, z) 的数量： 1. s = x + y + z （+ 表示字符串连接）； 2. t = x + y + ... + y + z （y 重复 k 次，k 为某个整数）。 输入输出数据格式： 输入： - 第一行包含两个整数 n 和 m（1 ≤ n < m ≤ 10^7），分别表示字符串 s 和 t 的长度。 - 第二行包含一个长度为 n 的字符串 s，由小写英文字母组成。 - 第三行包含一个长度为 m 的字符串 t，由小写英文字母组成。 输出： - 输出一个整数：满足条件的三元组 (x, y, z) 的数量。 示例： 输入： 4 8 abcd abcbcbcd 输出： 1 解释： 唯一有效的三元组是 (x, y, z) = ("a", "bc", "d")。实际上， - "abcd" = "a" + "bc" + "d"； - "abcbcbcd" = "a" + "bc" + "bc" + "bc" + "d"。