[Usaco2013]Necklace

时间限制:10s      空间限制:128MB

题目描述

给你一个长度为n的字符串A,再给你一个长度为m的字符串B,求至少在A中删去多少个字符才能使得B不是A的子串。注:该题只读入AB,不读入长度,先读入A,再读入B。数据保证AB中只含小写字母。

 


输入格式


输出格式


样例输入

ababaa
aba
 

样例输出

1
 
样例解释:
ababaa -> abbaa

提示

数据范围:
 n<=10000, m<=1000, m<=n


题目来源

Gold