石头剪子布

时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 117 总提交人数: 149

题目描述

石头Rock剪子Scissors布Paper。

想哥和叶姐又开始这个有趣的游戏。众所周知,他们俩的游戏不可能公平。他们分别给出自己出的序列(RSP分别代表石头、剪刀、布)。

想哥给出一个长度为n的序列,而叶姐给出长度为m的序列。$1 \le m < n \le 100,000$。叶姐显然有特权,她可以选择跳过想哥序列的一段开头,才开始将RSP序列进行匹配,以寻求从这一位置开始最多获胜次数。

请你帮叶姐求出这一次数,这就是想哥请17级吃饭的次数。显然,R胜S,S胜P,P胜R。

输入

第一行为n,m,含义如上。

接下来两行分别为想哥和叶姐的RSP序列。

输出

输出一行,最大获胜数

输入样例1

12 4
RSPPSSSRRPPR
RRRR

输出样例1

3

输入样例2

12 4
PPPRRRRRRRRR
RSSS

输出样例2

2

输入样例3

12 4
RRRRRRRRRSSS
RRRS

输出样例3

3

Hint

对于从哪里开始的匹配规则,请多参照样例2、3。

对于50%的数据,$n, m \le 4000$.(三方的算法就不要交了)

相关推荐