Submit: 65 Solved: 22

[Submit][Status][Web Board]

Amayama's friend Vince likes eating KFC. Now, Amayama gives a set of discount codes to Vince as a gift. However, Vince only wants the Original Recipe and he wishes to get as much Original Recipe discount codes as he can. Can you help him?

n and m, which indicate the length of the set of codes and the length of Original Recipe discount code. (1<=n<=1000000, 1<=m<=1000)

The second line is the set of codes.

The third line is the Original Recipe discount code.

The output contains an integer which is the number of Original Recipe discount codes that Vince can get.

```
15 2
lanranlanranlan
an
```

`5`

If you cut out a code, then this part of code should not be used again. Remember to adjust your KMP algorithm for this.