| Submit | All submissions | Best solutions | Back to list |
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
|
|||||||||
|
2016-10-11 21:24:51
@asshole: Asctivities are not one after another - they overlap, so there are N-K+1 activities in a string :) |
|||||||||
|
2016-10-11 19:43:25 asshole
I don't understand the question. since each activity is of k length shouldn't there the string length be multiple of k? |
|||||||||
|
2016-09-11 16:19:23 mehmetin
Accepted with PYPY, but WA with C++14... |
|||||||||
|
2016-09-11 09:23:03 Vipul Srivastava
what is the expected complexity of the solution? |
|||||||||
|
2016-09-10 21:00:51
Getting WA constantly anybody can please provide me a good test case to check my solution. Submission ID-17689065 Last edit: 2016-09-10 21:07:36 |
|||||||||
|
2016-09-09 18:55:06
Finally AC. Brilliant test cases.Shows how a problem is only as good as it's test cases :) |
|||||||||
|
2016-09-09 16:20:10
@aitya: Hello, well I'm slightly afraid you are failing only "big" test-cases :'( |
|||||||||
|
2016-09-09 14:53:48
i am constantly getting wa.Can you tell whether i am failing the most basic test cases or the corner ones submission ID-17680541 |
|||||||||
|
2016-09-07 22:39:14
@Vipul Srivastava: Hello, well I'm not sure, but in my opinion it might be caused by "memory" - putting all substrings to vector leads to storing of up to "2.5*10^9" characters which [I guess] is not suitable :) |
|||||||||
|
2016-09-07 19:13:39 Vipul Srivastava
I have tried multiple methods and still constantly getting SIGABRT in C++ |
|||||||||
RSS