石头剪子布

题目描述

石头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$.（三方的算法就不要交了）