8415: Necklace

内存限制:128 MB 时间限制:1 S
题面:传统 评测方式:文本比较 上传者:
提交:2 通过:1

题目描述

贝西收集了N颗石头,每颗石头上都有一个字母,贝西想把这些石头做成项链。

贝西的身边有另一只奶牛,这只奶牛的名字是一个长度为M的字符串,贝西不希望这只牛的名字出现在她的项链上(项链的子串),她想知道,最少删掉几颗石头就可以避免这种情况发生。

输入格式

* Line 1: The first line is a length-N string describing Bessie's initial necklace; each character is in the range "a" through "z".

* Line 2: The second line is the length-M name of the other cow in the barn, also made of characters from "a" to "z".

输出格式

* Line 1: The minimum number of stones that need to be removed from Bessie's necklace so that it does not contain the name of the other cow as a substring.

输入样例 复制

ababaa 
aba 

输出样例 复制

1 

数据范围与提示

For at least 20% of test cases, N <= 20. For at least 60% of test cases, N <= 1000, M <= 100. For all test cases, N <= 10000, M <= 1000. For all test cases, M <= N.

The modified necklace should be "abbaa".