CF1909G.Pumping Lemma

Tanchiky & 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$.

Tanchiky & Siromaru - Crystal Gravity

⠀

给定两个字符串 $s$ 和 $t$，长度分别为 $n$ 和 $m$。两个字符串均由小写英文字母组成。

统计满足以下条件的字符串三元组 $(x, y, z)$ 的个数：

• $s = x+y+z$（其中符号 $+$ 表示字符串连接）；
• $t = x+\underbrace{ y+\dots+y }_{k \text{ 次}} + z$，其中 $k$ 为某个整数。

The first line contains two integers $n$ and $m$ ($1 \leq n \lt 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.

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \lt m \leq 10^7$）—— 分别为字符串 $s$ 和 $t$ 的长度。

第二行包含一个长度为 $n$ 的字符串 $s$，由小写英文字母组成。

第三行包含一个长度为 $m$ 的字符串 $t$，由小写英文字母组成。

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

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

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"})$.

在第一个测试用例中，唯一有效的三元组是 $(x, y, z) = (\texttt{"a"}, \texttt{"bc"}, \texttt{"d"})$。事实上，

• $\texttt{"abcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"d"}$；
• $\texttt{"abcbcbcd"} = \texttt{"a"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"bc"} + \texttt{"d"}$。

在第二个测试用例中，共有 $5$ 个有效的三元组：

• $(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{""})$。

在第三个测试用例中，共有 $8$ 个有效的三元组：

• $(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"})$。