← 返回题目列表

AtCoder · awc0098_c

C. 高速公路折扣通行证

中文机器翻译题面 查看原题

分数: 366 分

问题陈述

高桥正要沿着一条漫长的高速公路行驶。这条高速公路有 N 收费站排成一排,编号从 1 to N,以及每个收费站 i 分配有一个由单个小写字母组成的识别码。当识别码 N 收费站按照编号顺序排列,一个字符串 获得 S 长度 N 。也就是说, i- 第一个字符 S 为收费站识别码 i.

高桥必须从收费站经过所有收费站 1 前往收费站 N 按其数字升序排列。通常情况下,通过每个收费站需要的行程时间为 1,因此在没有任何优化的情况下,总行程时间为 N.

不过,高桥有折扣通行证。折扣通行证由字符串表示 T 长度 M。使用这张折扣通行证,或许可以准确通行 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).

高桥可以选择 0 或更多区间可申请折扣通行证,但所选的两个区间不得共用一个收费站。一个区间的最后一个收费站和另一个区间的第一个收费站可以具有连续的编号(即相邻)。

不包含在适用折扣通行证的任何区间内的收费站均单独通过,每个收费站的行驶时间为 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
  • 第一行包含一个整数 N 代表收费站的数量和一个整数 M 代表折扣通行证的长度,以空格分隔。
  • 第二行包含一个字符串 S 长度 N,按编号顺序排列的收费站的识别码。
  • 第三行包含一个字符串 T 长度 M,代表折扣通行证。

输出

在一行中输出高桥通过所有收费站的最短总行程时间。


示例输入 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