codeforces#P1909G. Pumping Lemma

Pumping Lemma

Description

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

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

4 8
abcd
abcbcbcd
3 5
aaa
aaaaa
12 16
abbababacaab
abbababababacaab
1
5
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"})$.