This article presents an algorithm that solves an on-line version of the longest common subsequence (LCS) problem for two strings over a constant alphabet in O(d+n) time and O(m+d) space, where m is the length of the shorter string, the whole of which is given to the algorithm in advance, n is the length of the longer string, which is given as a data stream, and d is the number of dominant matches between the two strings. A new upper bound, O(p(m-q)), of d is also presented, where p is the length of the LCS of the two strings, and q is the length of the LCS of the shorter string and the m-length prefix of the longer string.

For any m strings of total length n, we propose an O(mn log n)-time, O(n)-space algorithm that finds a maximal common subsequence of all the strings, in the sense that inserting any character in it no longer yields a common subsequence of them. Such a common subsequence could be treated as indicating a nontrivial common structure we could find in the strings since it is NP-hard to find any longest common subsequence of the strings.

A linear-time constructible data structure for a real number sequence supporting O(1)-time queries of the maximal local maximum-sum segment of any contiguous subsequence containing any specific position is proposed, where a local maximum-sum segment is a segment whose maximum-sum segment is itself.