P12129 [蓝桥杯 2024 省 B 第二场] 遗迹（加强版）

与原题相比，去除了【数据保证随机】。

小蓝找到了一个外星文明留下来的遗迹，遗迹大门的屏幕上有一个长度为 $m$ 的字符串 $t$ 和一个输入框，下面还有一个键盘，键盘为一个长度为 $n$ 的字符串 $s$ ，由一个可以横向移动的指针来敲击键盘，指针可以向左移或向右移，不能移出键盘。 小蓝需要在键盘字符串 $s$ 上先指定指针初始位置然后不断移动指针的位置，过程中通过敲击指针所在的字符来进行输入。然而，指针最多只能移动 $L$ 的距离，小蓝想输入一个尽可能长的一个 $t$ 的前缀，请问他最多能输入多少位。

输入的第一行包含三个正整数 $n, m, L$，相邻整数之间使用一个空格分隔。 第二行包含一个长度为 $n$ 的字符串 $s$。 第三行包含一个长度为 $m$ 的字符串 $t$。

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

### 样例说明 初始选择指针位于键盘 $\tt{abc}$ 上的 $\tt{a}$，输入 $\tt{acbbac}$ 这 $6$ 个字符分别需要指针移动 $0, 2, 1, 0, 1, 2$ 的距离，而最大移动距离为 $5$，所以最多输入 $5$ 个字符，移动 $0 + 2 + 1 + 0 + 1 = 4$ 的距离。 ### 评测用例规模与约定 - 对于 $20\%$ 的评测用例，$1 \leq m \leq 20$； - 对于所有评测用例，$1 \leq n \leq 10^3$，$1 \leq m \leq 10^5$，$1 \leq L \leq 10^9$ 且 $s, t$ 中只包含小写字母，且 $s$ 中一定包含所有 $t$ 中出现过的字母。