CSG-CPC
Online Judge

1215 : 室温超导

         Time Limit: 2 Sec     Memory Limit: 512 Mb     Submitted: 39     Solved: 3    

Description

存在两个长度分别为 \(n\)\(m\) 的字符串 \(S\)\(T\)

小A为了检验 \(S\)\(T\) 是否能合成室温超导材料,对 \(S\) 的任意非空子串 \(S[i...j]\),在 \(T\) 中选取任意长度不超过 \(n-j+1\) 的后缀与其拼接,得到测试样品,再进行下一步的超导测试。即测试样品的一种合成方式为 \(S[i...j] + T[k...m]\),满足\(1 \leq i \leq j \leq n,1 \leq k \leq m\),且 \(m-k \leq n-j\)

为了能尽快完成实验,小A想知道在所有的合成方式中,最终能得到的不同测试样品的数量。

Input

第一行两个整数 \(n\)\(m\),分别代表 \(S\)\(T\) 的长度\((1\leq m\leq n\leq 500000)\)

第二、第三行为两个字符串,代表 \(S\)\(T\)

\(S\)\(T\) 只包含小写字母

Output

一个整数,表示不同测试样品的数量。

Sample

3 2
aab
bc

##CASE##
4 3
abca
bba
5

##CASE##
16

Hint

样例一:

\(S[1,1]\) 可以合成 abc, ac

\(S[2,2]\) 可以合成 abc, ac

\(S[3,3]\) 可以合成 bc

\(S[1,2]\) 可以合成 aabc, aac

\(S[2,3]\) 可以合成 abc

\(S[1,3]\) 可以合成 aabc

一共可以得到 ac, bc, abc, aac, aabc 5种不同的测试样品