Problem 1067 --吃一吃

1067: 吃一吃

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 223  Solved: 55
[Submit][Status][Web Board][Creator:]

Description

zyyyyy 喝了药以后感觉很苦,发现这个药竟然是无糖的,哼!于是他决定吃一些甜甜的小饼干。
zyyyyy 在实验室转了一圈,从 gungun 的桌子上偷了一包字母饼干准备开吃~
当然 zyyyyy 可不是不懂感恩的人!他决定给 gungun 留下一条非常重要的消息帮助她AK比赛 !
一条消息定义为一个不为空的字符串,
而 zyyyyy 不断地取出饼干,实际上也组成了一个字符串。
生病的 zyyyyy 非常地制杖,他现在只会按顺序匹配了!如下所示,背景黄色的字母会被作为消息:

饼干 THANHAKYONUVERYMUCHKYOUVERYMUCH    剩下12块饼干

或者 THANHAKYONUVERYMUCHKYOUVERYMUCH    剩下0块饼干

消息 THANKYOUVERYMUCH

若您已理解何为按顺序匹配,可以跳过下面这段话以节省您的时间。

他的操作步骤可以形式化地描述为:
1. 从袋子里取出一块饼干。如果取之前袋子已空,结束。如果这块饼干是消息当前需要的字母,可以转到2或者3;否则,转到3
2. 将这块饼干放到桌面上。如果放下后消息已经完整,结束;否则,消息当前需要的字母变为下一个,转到1
3. 吃掉这块饼干,转到1
初始时,消息需要的字母为第一个字母,即上例中的"T"

这时候,wenwenla 进来了,不可思议的 wenwenla 已经预测到了 zyyyyy 拿出饼干的所有顺序,
现在他想知道 zyyyyy 留下重要的消息后袋子里最多还剩下多少饼干,以决定帮不帮 gungun 打死 zyyyyy 。

Input

第一行两个整数n和m,分别表示两个串的长度。
第二行一个字符串,表示取饼干的顺序。
第三行一个字符串,表示一条消息。
m ≤ n ≤ 1000000,字符串不为空,且仅含大写字母。

Output

一个整数,表示结束时袋子里最多还剩下多少饼干。

Sample Input

31 16
THANHAKYONUVERYMUCHKYOUVERYMUCH
THANKYOUVERYMUCH

Sample Output

12

HINT

准确的题意:主串取出一个与模式串相同的子序列,且最后一位的位置要尽量在前
此外,存在不能留下完整消息的情况,此时显然是输出 0

Source

[Submit][Status]