Search

Given two strings X and Y and a constraining string P, a string Z is called a constrained longest common subsequence of X and Y with respect to P if Z is the longest common subsequence of X and Y such that P is a subsequence of Z. In this paper, we propose an O(r x min{mN, nM})-time algorithm for solving this problem, where m, n and r are the lengths of X, Y and P, respectively, and M and N are the number of runs of the run-length-encoded strings of X and Y, respectively. [ABSTRACT FROM AUTHOR]

An ordered tree is called a non-regular tree with a prescribed branching sequence (or non-regular tree for short) if its internal nodes have a prespecified degree sequence in preorder list. We define a concise representation, called right distance sequences to describe such trees. A coding tree helps us to systematically investigate the structural representation of non-regular trees. Consequently, we present a loopless algorithm to generate Gray-codes of non-regular trees using right distance sequences. [ABSTRACT FROM PUBLISHER]