Hi,
I'm trying to solve this problem from SPOJ.
My idea is to run Aho-corasick algorithm to find all intervals [a,b] in the text which contains one word from the dictionary and then to run a greedy interval scheduling to find the maximum number of non overlapping intervals.If this count is <=k ,I'm outputting it as answer.else I am outputting ( k+1) as k noises can accommodate k+1 words at max,So,if we have number of non overlapping intervals > k+1 we can just consider some of those words as noises and can find k+1 words.I think the last greedy decision part is causing me WA.
I'll be very happy if somebody can point out my mistake.This is the first time I'm using Aho-Corasick algorithm,so not much experience as such.
I believe, correct me if i am wrong, that since the maximum length of a word is 20, you can apply the rolling hashing algorithhm and generate all hashes of substrings of length( 1, 2, ... , maxL ) on the original string. Since the aho-corasick algorithm is quite tricky to implement, i think you can try this approach.
I think my aho corasick implementation is not wrong.But the later part has some wrong logic.Also,I don't know rolling hashing well.Will go through it.thanks! :)
The problem is probably solvable with some sort of dp algorithm. I don't know whether your logic is correct or not, but if you can find a dp algorithm with an appropriate complexity, i think you should go for it.
Anyway, I wish you good luck and a happy new year :)
Ya I think so!!!Happy new Year!!!!Happy Coding!! :)
You can do this by using DP. Consider the state as (n, k, run) , where n is the position in the string where you are currently, k is the remaining number of noises , run is true/false iff the previous character was considered as noise.For the transitions , you can either start a word at this character OR consider this character as noise. For the first transition , a trie or a hash table will work. Complexity:- O(N * K * 20 * 2)
Ok thank you..I'll try :)