ADACLEAN - Ada and Spring Cleaning

Ada the Ladybug has decided to do some "Spring Cleaning". As you might know, she keeps a TODO list. She is very sparing so she keeps all her activities as one string. You might get very confused while reading the string but she has a system - every activity has length exactly K characters. Sadly, as new activities were added to the list many duplicities appeared. Now it is time to find out how many unique activities are in her TODO list.

Input

First line contains T, number of test-cases.

Each test-case begins with N, K, 1 ≤ K ≤ N ≤ 105, length of string and length of activities respectively.

Next line consists of string of length N, consisting of lowercase letters.

The sum of lengths of strings among all test-cases won't exceed 3*105

Output

For each test-case, print the number of unique substrings of length K

Example Input

5
3 2
aaa
5 1
abcba
4 2
abac
10 2
abbaaaabba
7 3
dogodog

Example Output

1
3
3
4
4

Added by:Morass
Date:2016-09-06
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU

hide comments
2017-02-07 16:40:54 Jamil Siam
Great hashing problem!
2017-01-28 23:50:19
@rajat_007: Good day to you, well you can generate them yourself (you can use for example following [simplified] generator - to make random big testcases) http://pastebin.com/Es61Bez4 {I can't give-out judge data, so you have to do it more-or-less yourself :P }

GL ^_^
2017-01-28 17:06:16
please provide some big test cases.... I am not able to find test cases anywhere else
2017-01-27 03:38:11
@rajat_007: Sorry, no clue - don't understand Java :/

Here is some NZEC topic [ http://stackoverflow.com/questions/24571469/getting-an-nzec-error-in-spoj-for-this-code ]

When I execute the file (it fails) locally, I get output "normally" so no clue where is problem.

It also says:

Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

But I have no clue what it means :/

**EDIT → When I removed following lines:

for(int i=0;i<=n-k;i++)
{
String b=a.substring(i,i+k);
sh.add(b);
}

I got "WA" instead of "RTE" - so I guess there might be some "space overflow?" or something like that :O - dunno

Last edit: 2017-01-27 03:43:01
2017-01-26 22:58:20
Getting NZEC runtime error ? Dont know why ... Please Help
Submission ID: 18649514
2017-01-04 04:22:30 Khanh Ninh
Thank for the help ! I got AC :D
2017-01-03 21:58:53
@Khanh Ninh:
Hello,

it seems there is some "fail" with cleaning. You are failing on a testcase, but when executed on the testcase alone, you passed.

PS: (cleaning one array got me AC - so go for it :P )
2017-01-03 15:04:46 Khanh Ninh
Hi, I'm having an unknown WA too, may you check the code? ID:18506949
2016-10-30 00:28:15
@Palashvijay4O: Good day to you - you are failing some "big" test-cases. Your answer are "lower" and when I change modulo the answers changes too.

So - maybe the algorithm is not bad (yet I can't be sure), yet you shall try "double hashing" instead [the probability of failure is much lesser]

But since the test-cases are too big, this is just my opinion :)

Have nice day & Good Luck!
2016-10-29 23:29:05 Palashvijay4O
getting WA.. dont know what's the issue.
Id - 18058212
Please check once. TIA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.