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.