| 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
|
|||||||||
|
2019-05-28 13:32:35
. If the hashes are equal (hash(s)=hash(t)), then the strings do not necessarily have to be equal.Keep This in mind Good Luck. |
|||||||||
|
2019-04-11 20:41:55
AC in 1 go ezz segment tree |
|||||||||
|
2019-04-04 10:55:18
if this problem quite hard, you can check out the hint: https://spoj-solution.github.io/2019/03/31/ADACLEAN.html |
|||||||||
|
2018-05-28 19:24:09
@morass Can you please check the solution 21741453 . It is showing TLE . Can you please explain me the reason . Thank You . |
|||||||||
|
2018-02-25 14:07:58
Can you please check 21232915. It exceeds time limit. Maybe some problem with hash function. I self reviewed many times, cant find mistake. Also have other fast solution 21241622, but still TLE Last edit: 2018-02-28 17:10:28 |
|||||||||
|
2018-01-03 00:04:46
@morass: I am getting WA , could you tell me where the code is failing id =20889399 |
|||||||||
|
2017-10-16 07:41:05
1 am getting TLE can anyone tell me expected TC |
|||||||||
|
2017-09-29 20:19:40
thanks morass...I was missing one memset statement....did it with sa.... |
|||||||||
|
2017-09-29 13:26:17
@starbot: Good day to you, try following test-case: 2 2 1 mm 1 1 m Seems your program prints "0" for the second case (even though 0 is not possible). Also it seems it works properly if it is the only input (so perhaps some garbage remaining from previous test-cases). Good Luck & Have Nice Day |
|||||||||
|
2017-09-28 22:27:55
@Morass could you tell me where I am failing id = 20253140 |
|||||||||
RSS