B - Sushisushi Ruins Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

表示言語

/ /

Score : 100 points

Problem Statement

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.

Constraints

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

Input

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

N M
S
T

Output

Output the number of distinct valid restoration methods.

Sample Input 1

4 4
scsc
scpc

Sample Output 1

8

表示言語

/ /

Score : 100 points

문제

고고학자 김석구는 스시스시 유적에서 발견된 비문을 연구하고 있다.

현재 연구하고 있는 유적의 석판에는 길이 N인 문자열 S가 새겨져 있으며, 학자들은 길이 M인 문자열 T가 비문 속에 나타나 있다고 추정하고 있다.

오랜 시간에 걸쳐 비문이 훼손되면서 원래 새겨져 있던 문구의 일부는 통째로 사라졌다고 한다. 여러분은 다음과 같은 방법으로 문자열을 복원하려고 한다.

  1. T에서 길이가 K인 부분문자열을 지운다. (1 \leq K < M)

  2. 지운 뒤의 문자열이 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 が碑文の中に現れていると推定している．

長い時間が経つうちに，もともと刻まれていた文句の一部はまるごと消えてしまったという．あなたは次の方法で文字列を復元しようとしている．

  1. T から長さ K の部分文字列を削除する．(1 \leq K < M)

  2. 削除後の文字列が S の部分文字列として現れるなら，有効な復元方法であるという．

互いに異なる有効な復元方法の個数を求めよ．削除した部分文字列の長さ，削除した位置，削除後の文字列が S の部分文字列として現れる位置のうち，少なくとも 1 つが異なれば異なる復元方法である．

制約

  • 1 \leq N, M \leq 200\,000
  • S と T はどちらも英小文字のみからなる
  • 入力される数値はすべて整数

入力

入力は以下の形式で標準入力から与えられる．

N M
S
T

出力

互いに異なる有効な復元方法の個数を出力せよ．

入力例 1

4 4
scsc
scpc

出力例 1

8