题目描述

给定两个串 $s$（长度为 $N =|s|$ ） , $t$ （长度为 $M=|t|$），初始有一个空串 $p$。每次可以选出一个 $s$ 的子串拼到 $p$ 后面。

求最少的操作次数使得最终 $p=t$。

输入格式

第一行两个整数 $N \ M ( 1 \le N,M \le 5×10^4)$

下来 N 个字母，表示字符串 s，可能分多行输入，每行不超过80个字母。

下来 M 个字母，表示字符串 t，可能分多行输入，每行不超过80个字母。

输出格式

一行一个整数，表示最少的操作步数。

输入输出样例 #1

输入 #1

38 9 
THEQUICKBROWNFOXDO 
GJUMPSOVERTHELAZYDOG 
FOXDOG 
DOG

输出 #1

2