表示言語
/ /分数: 100 点
问题陈述
考古学家 seokgukim 正在研究在 Sushisushi 遗址发现的铭文。
目前正在研究的石碑有一根绳子 其上刻有 S 长度 N ,学者认为有一根绳子 铭文中出现 T 长度 M 。
在很长一段时间内,据说最初雕刻的文字的某些部分已经完全消失。您想使用以下方法恢复字符串。
-
删除长度为 的子串 K 来自 T. (1 \leq K < M)
-
如果删除后的字符串出现为 S,这称为有效的恢复方法。
查找不同的有效恢复方法的数量。如果以下至少一项不同,则认为两种有效的恢复方法不同:删除的子字符串的长度、删除的子字符串的位置或删除后的字符串作为子字符串出现的位置 S.
约束
- 1 \leq N, M \leq 200\,000
- 两者 S 和 T 仅由小写英文字母组成。
- 所有给定的数字都是整数。
输入
输入由标准输入按以下格式给出:
N M S T
输出
输出不同的有效恢复方法的数量。
示例输入 1
4 4 scsc scpc
示例输出 1
8
表示言語
/ /分数: 100 点
문제
고고학자 김석구는 스시스시 유적에서 발견된 비문을 연구하고 있다.
현재 연구하고 있는 유적의 석판에는 길이 N인 문자열 S가 새겨져 있으며, 학자들은 길이 M인 문자열 T가 비문 속에 나타나 있다고 추정하고 있다.
오랜 시간에 걸쳐 비문이 훼손되면서 원래 새겨져 있던 문구의 일부는 통째로 사라졌다고 한다. 여러분은 다음과 같은 방법으로 문자열을 복원하려고 한다.
-
T에서 길이가 K인 부분문자열을 지운다. (1 \leq K < M)
-
지운 뒤의 문자열이 S의 부분문자열로 나타나면 유효한 복원 방법이라고 한다.
서로 다른 유효한 복원 방법의 개수를 구해 보자. 지운 부분문자열의 길이, 지운 위치, S의 부분문자열로 나타난 위치 중 하나라도 다르면 다른 복원 방법이다.
제한
- 1 \leq N, M \leq 200\,000
- S와 T는 모두 알파벳 소문자로만 이루어져 있다.
- 입력으로 주어지는 수는 모두 정수이다.
입력
입력은 다음 형식으로 표준 입력으로 주어진다.
N M S T
출력
서로 다른 유효한 복원 방법의 개수를 출력한다.
입력 예 1
4 4 scsc scpc
출력 예 1
8