Necklace

Interview

Time limit1sMemory limit128 MB

Summary

Given a string and a pattern, delete the fewest characters so the pattern no longer appears as a contiguous substring.

Level: Medium7 of 10
Topics: Dynamic programming, String matching, String, Prefix sum
Solved: No attempts yet

Problem

Bessie the cow has laid out a row of $N$ rocks, each painted with a single lowercase letter, to build into a fashionable necklace. Reading the rocks in order gives a string of length $N$ .

Being protective of her belongings, Bessie does not want to share her necklace with the other cow living on her side of the barn. That cow's name is a string of $M$ characters, and Bessie wants to be sure this length- $M$ string never appears as a contiguous substring of her necklace (otherwise the other cow might mistakenly think the necklace is hers). Bessie decides to remove some rocks so that the other cow's name does not appear as a substring. (When rocks are removed, the remaining rocks keep their original order and join into the new necklace string.)

Determine the minimum number of rocks Bessie must remove.

Input

Line 1: a string of length $N$ describing Bessie's initial necklace; each character is between a and z.
Line 2: the length- $M$ name of the other cow in the barn, also made of characters from a to z.

Output

Line 1: the minimum number of rocks that must be removed from Bessie's necklace so that it does not contain the other cow's name as a substring.

Constraints

$1 \le M \le N \le 10000$
$M \le 1000$
Every character of the necklace and the name is a lowercase letter from a to z.

Examples5

Example 1
Input
```
ababaa
aba
```
Expected output
```
1
```
Example 2
Input
```
abcde
xyz
```
Expected output
```
0
```
Example 3
Input
```
aaaa
a
```
Expected output
```
4
```
Example 4
Input
```
abcabc
b
```
Expected output
```
2
```
Example 5
Input
```
aaaa
aa
```
Expected output
```
3
```