| 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
|
|||||||||
|
2017-08-15 09:45:54 Avik Sarkar
AC in 1 GO ... Nice Hashing Problem . ... |
|||||||||
|
2017-05-06 12:43:54
@jacastrorug97: Good day to you! SPOJ just works in such way, than it executes all test-cases even though it fails on some of them. So well. .. even though you see test-case 15, the WA is on test-case 1. Good Luck |
|||||||||
|
2017-05-06 01:20:51
Case 15 ? Last edit: 2017-05-06 01:23:10 |
|||||||||
|
2017-04-17 00:38:17
@hodobox: Hello, well I guess it is Birthday Paradox's fault ^_^ Have nice day! |
|||||||||
|
2017-04-15 16:50:23
I have no idea how you managed it, but I got false collisions with a random prime mod > 2*10^9. That's pretty good. |
|||||||||
|
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 |
|||||||||
RSS