12751275 SUSTech Online Judge
Problem 1275 --Discount!

1275: Discount!

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 66  Solved: 23
[Submit][Status][Web Board]

Description

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?

Input

The first line contains two integer 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.


Output

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

Sample Input

15 2
lanranlanranlan 
an

Sample Output

5

HINT

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

Source

 

[Submit][Status]