Preparing NOJ

String

1000ms 32768K

Description:

Given a string S and two integers L and M, we consider a substring of S as “recoverable” if and only if
  (i) It is of length M*L;
  (ii) It can be constructed by concatenating M “diversified” substrings of S, where each of these substrings has length L; two strings are considered as “diversified” if they don’t have the same character for every position.

Two substrings of S are considered as “different” if they are cut from different part of S. For example, string "aa" has 3 different substrings "aa", "a" and "a".

Your task is to calculate the number of different “recoverable” substrings of S.

Input:

The input contains multiple test cases, proceeding to the End of File.

The first line of each test case has two space-separated integers M and L.

The second ine of each test case has a string S, which consists of only lowercase letters.

The length of S is not larger than 10^5, and 1 ≤ M * L ≤ the length of S.

Output:

For each test case, output the answer in a single line.

Sample Input:

3 3
abcabcbcaabc

Sample Output:

2

Info

HDU

Provider HDU

Origin 2013 Asia Regional Changchun

Code HDU4821

Tags

Submitted 50

Passed 11

AC Rate 22%

Date 06/03/2019 16:46:11

Related

Nothing Yet