Dotcpp  >  编程题库  >  蓝桥杯2024年第十五届省赛真题-遗迹
题目 3246:

蓝桥杯2024年第十五届省赛真题-遗迹

时间限制: 2s 内存限制: 512MB 提交: 345 解决: 30

题目描述

小蓝找到了一个外星文明留下来的遗迹,遗迹大门的屏幕上有一个长度为m 的字符串 t 和一个输入框,下面还有一个键盘,键盘为一个长度为 n 的字符串 s ,由一个可以横向移动的指针来敲击键盘,指针可以向左移或向右移,不能移出键盘。

小蓝需要在键盘字符串 s 上先指定指针初始位置然后不断移动指针的位置,过程中通过敲击指针所在的字符来进行输入。然而,指针最多只能移动 L 的距离,小蓝想输入一个尽可能长的一个 t 的前缀,请问他最多能输入多少位。

输入格式

输入的第一行包含三个正整数 n, m, L ,相邻整数之间使用一个空格分隔。

第二行包含一个长度为 n 的字符串 s 。

第三行包含一个长度为 m 的字符串 t 。

输出格式

输出一行包含一个整数表示答案。

样例输入

3 6 5
abc
acbbac

样例输出

5

提示

【样例说明】

初始选择指针位于键盘 abc 上的 a ,输入 acbbac 这 6 个字符分别需要指针移动 0, 2, 1, 0, 1, 2 的距离,而最大移动距离为 5 ,所以最多输入 5 个字符,移动 0 + 2 + 1 + 0 + 1 = 4 的距离。

【评测用例规模与约定】

对于 20% 的评测用例,1 ≤ m ≤ 20;

对于所有评测用例,1 ≤ n ≤ 103 ,1 ≤ m ≤ 105 ,1 ≤ L ≤ 109 且 s, t 中只包含小写字母,且 s 中一定包含所有 t 中出现过的字母,数据保证随机。

标签