Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds

Florin Manea, Jonas Richardsen, Markus L. Schmid

For two strings u, v over some alphabet A, we investigate the problem of embedding u into w as a subsequence under the presence of generalised gap constraints. A generalised gap co…