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.

[Submit][Status]