C - Highway Discount Pass Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は車で長い高速道路を走ろうとしています。この高速道路には N 個の料金所が 1 から N まで番号順に一列に並んでおり、料金所 i にはアルファベット小文字 1 文字からなる識別コードが割り当てられています。N 個の料金所の識別コードを番号順に並べると、長さ N の文字列 S が得られます。すなわち、S の i 文字目が料金所 i の識別コードです。

高橋君は料金所 1 から料金所 N まで、すべての料金所を番号の昇順に通過しなければなりません。通常、料金所を 1 つ通過するごとに所要時間 1 がかかるため、何も工夫しなければ合計所要時間は N です。

しかし、高橋君は割引パスを持っています。割引パスは長さ M の文字列 T で表されます。この割引パスを使うと、連続するちょうど M 個の料金所をまとめて所要時間 1 で通過できる場合があります。割引パスは何度でも使うことができますが、適用する区間同士は重なってはいけません。

具体的には、割引パスの適用条件は次の通りです。連続する M 個の料金所からなる区間、すなわち料金所 l, l+1, \ldots, l+M-1（1 \leq l \leq N-M+1）について、その識別コードを順に並べた文字列（S の l 文字目から l+M-1 文字目までの部分文字列）が T と一致しているとき、その区間に割引パスを適用できます。適用すると、その M 個の料金所をまとめて所要時間 1 で通過できます（通常なら所要時間 M かかるところが所要時間 1 になります）。

高橋君は割引パスを適用する区間を 0 個以上いくつでも選べますが、選んだどの 2 つの区間も共通する料金所を持ってはいけません。ある区間の末尾の料金所と別の区間の先頭の料金所の番号が連続していること（隣り合うこと）は問題ありません。

割引パスを適用した区間に含まれない料金所は、1 つにつき所要時間 1 をかけて個別に通過します。割引パスを適用した区間の数を k とすると、合計所要時間は k + (N - kM) = N - k(M - 1) です。

高橋君がすべての料金所を通過するのにかかる最小の合計所要時間を求めてください。

制約

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • N, M は整数
  • S は長さ N の英小文字からなる文字列
  • T は長さ M の英小文字からなる文字列

入力

N M
S
T
  • 1 行目には、料金所の数を表す整数 N と、割引パスの長さを表す整数 M が空白区切りで与えられる。
  • 2 行目には、料金所の識別コードを番号順に並べた長さ N の文字列 S が与えられる。
  • 3 行目には、割引パスを表す長さ M の文字列 T が与えられる。

出力

高橋君がすべての料金所を通過するのにかかる最小の合計所要時間を 1 行で出力せよ。

入力例 1

8 3
abcxxabc
abc

出力例 1

4

入力例 2

5 2
aaaaa
aa

出力例 2

3

入力例 3

30 4
abcaabcaabxabcayzabcaabcaqqqrr
abca

出力例 3

15

入力例 4

100 5
abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
abcde

出力例 4

20

入力例 5

1 1
a
a

出力例 5

1

Score : 366 pts

Problem Statement

Takahashi is about to drive along a long highway. This highway has N toll gates lined up in a row, numbered from 1 to N, and each toll gate i is assigned an identification code consisting of a single lowercase alphabet letter. When the identification codes of the N toll gates are arranged in order of their numbers, a string S of length N is obtained. That is, the i-th character of S is the identification code of toll gate i.

Takahashi must pass through all toll gates from toll gate 1 to toll gate N in ascending order of their numbers. Normally, passing through each toll gate takes a travel time of 1, so without any optimization, the total travel time is N.

However, Takahashi has a discount pass. The discount pass is represented by a string T of length M. By using this discount pass, it may be possible to pass through exactly M consecutive toll gates together with a travel time of 1. The discount pass can be used any number of times, but the intervals to which it is applied must not overlap.

Specifically, the conditions for applying the discount pass are as follows. For an interval consisting of M consecutive toll gates, namely toll gates l, l+1, \ldots, l+M-1 (1 \leq l \leq N-M+1), if the string formed by arranging their identification codes in order (the substring of S from the l-th character to the (l+M-1)-th character) matches T, then the discount pass can be applied to that interval. When applied, those M toll gates can be passed together with a travel time of 1 (instead of the usual travel time of M).

Takahashi can choose 0 or more intervals to apply the discount pass, but no two chosen intervals may share a common toll gate. It is fine for the last toll gate of one interval and the first toll gate of another interval to have consecutive numbers (i.e., be adjacent).

Toll gates not included in any interval where the discount pass is applied are passed individually, each taking a travel time of 1. If the number of intervals where the discount pass is applied is k, the total travel time is k + (N - kM) = N - k(M - 1).

Find the minimum total travel time for Takahashi to pass through all toll gates.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq M \leq N
  • N, M are integers
  • S is a string of length N consisting of lowercase English letters
  • T is a string of length M consisting of lowercase English letters

Input

N M
S
T
  • The first line contains an integer N representing the number of toll gates and an integer M representing the length of the discount pass, separated by a space.
  • The second line contains a string S of length N, which is the identification codes of the toll gates arranged in order of their numbers.
  • The third line contains a string T of length M, representing the discount pass.

Output

Output in one line the minimum total travel time for Takahashi to pass through all toll gates.

Sample Input 1

8 3
abcxxabc
abc

Sample Output 1

4

Sample Input 2

5 2
aaaaa
aa

Sample Output 2

3

Sample Input 3

30 4
abcaabcaabxabcayzabcaabcaqqqrr
abca

Sample Output 3

15

Sample Input 4

100 5
abcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcdeabcde
abcde

Sample Output 4

20

Sample Input 5

1 1
a
a

Sample Output 5

1