On minimizing pattern splitting in multi-track string matching

Given a pattern string P=p1p2⋯pm and K parallel text strings T={Tk=t1k⋯tnk|1⩽k⩽K} over an integer alphabet Σ, our task is to find the smallest integer κ>0 such that P can be split into κ pieces P=P1…Pκ, where each Pi has an occurrence in some text track Tki 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.