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

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 a single integer: the number of valid triples $(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"})$ .