##
On Finding Minimum Splitting of Pattern in Multi-Track String Matching

####
Kjell Lemström and Veli Mäkinen

Given a pattern string *P = p_1 ... p_m* and *K* parallel text strings
*T^{k} = t^{k}_{1} ... t^{k}_{n}, 1 <= k <= K*, over an integer
alphabet, our task is to find the smallest integer *s>0* such that
*P* can be split into s pieces *P = P^{1} ... P^{s}*, where each
*P^{i}* has an occurrence in some text track *T^{k_{i}}* and these
partial occurrences retain the order.
We study some variations of this minimum splitting problem,
such as splittings with limited gaps and transposition
invariance, and show how to use sparse dynamic
programming to solve the variations efficiently.
In particular, we show that the minimum splitting problem
can be interpreted as a shortest path problem on line segments.