| 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
|
|||||||||
|
2024-06-23 10:49:13
Note: take care of overflow |
|||||||||
|
2022-08-22 19:25:18
No need of using two hash function. Using only base 29 and mod as 2^(63)-1 is enough |
|||||||||
|
2022-01-19 13:05:50
Use two different modulo multiplicator, for avoiding collision, i used p1=31 and other p2=53 and got accepted |
|||||||||
|
2022-01-19 13:04:43
Used, rabin karp algo and two hash functions, used set<pair<int,int>>, |
|||||||||
|
2021-10-08 18:50:03
classic RabinKarp .. consider using 2 hash functions |
|||||||||
|
2021-01-06 18:04:09
HINT: Use prime number 2^{63} - 1 and modular multiplication if you want to use string hashing. |
|||||||||
|
2020-10-29 11:54:06
cost me 12 WAs with 12 different hashing schemes to get to the correct one. |
|||||||||
|
2020-10-14 00:47:12
To avoid WA use two hash functions!!! |
|||||||||
|
2020-09-20 06:15:23
Use mod value as 1e18+9 to avoid WA Last edit: 2020-09-20 06:21:26 |
|||||||||
|
2020-08-17 09:16:22
AC in one go. |
|||||||||
RSS