Hi,
I'm trying to solve this problem from SPOJ.
SPOJ-TREEBA
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.
Full text and comments »