1215 : 室温超导
Time Limit: 2 Sec Memory Limit: 512 Mb Submitted: 39 Solved: 3Description
存在两个长度分别为 \(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种不同的测试样品