AT_scpc2026_div1_b.Sushisushi Ruins

Archaeologist seokgukim is studying an inscription discovered at the Sushisushi ruins.

The stone tablet currently being studied has a string $S$ of length $N$ engraved on it, and scholars believe that a string $T$ of length $M$ appears in the inscription.

Over a long period of time, some part of the originally engraved text is said to have disappeared entirely. You want to restore the string using the following method.

1. Delete a substring of length $K$ from $T$. ($1 \leq K < M$)

2. If the string after deletion appears as a substring of $S$, this is called a valid restoration method.

Find the number of distinct valid restoration methods. Two valid restoration methods are considered different if at least one of the following differs: the length of the deleted substring, the position of the deleted substring, or the position where the string after deletion appears as a substring of $S$.

考古学家石国金正在研究在寿司寿司遗址发现的一块铭文。

目前研究的石碑上刻有一长度为 $N$ 的字符串 $S$，学者们认为其中包含一长度为 $M$ 的字符串 $T$。

经过漫长岁月，原始铭文中某一部分据称已完全消失。你需采用以下方法恢复该字符串：

1. 从 $T$ 中删除一个长度为 $K$ 的子串（$1 \leq K < M$）；
2. 若删除后的字符串作为子串出现在 $S$ 中，则称该恢复方法为有效恢复方法。

求不同有效恢复方法的总数。若两种有效恢复方法满足以下任一条件，则视为不同：被删除子串的长度不同、被删除子串在 $T$ 中的位置不同，或删除后所得字符串在 $S$ 中作为子串出现的位置不同。

The input is given from Standard Input in the following format:

$N$ $M$
$S$
$T$

输入从标准输入中按以下格式给出：

$N$ $M$
$S$
$T$

Output the number of distinct valid restoration methods.

输出不同的有效恢复方法的数量。

表示言語

/ /

Constraints

• $1 \leq N, M \leq 200\,000$
• Both $S$ and $T$ consist only of lowercase English letters.
• All given numbers are integers.

表示语言

/ /

限制条件

• $1 \leq N, M \leq 200\,000$
• 字符串 $S$ 和 $T$ 均仅由小写英文字母组成。
• 所有给定的数均为整数。