I am doing a project on data mining.
I have a very large string of size, say
n and many small strings,
l_1,l_2.. each of size at most
m. I want to find the sequence of small strings such that their concatenation has the minimum alignment cost (costs can include insertion, deletion and substitution) with my large string of size
n. I can use one string more than once and it is not mandatory to use all the strings. Note that
m << n
My greedy implementation gives very bad results even for small strings. I can't find an efficient solution to this problem. Can anyone help?
It looks like dynamic programming might be able to help but I'm not sure.