An Efficient Algorithm for the Longest Pattern Subsequence Problem

摘要

This paper studies the longest pattern subsequence problem based on the dynamic programming algorithm. An O(n{sup}2) time algorithm for the problem is firstly presented. Then the presented algorithm is improved further by generalizing the RSK algorithm and the standard Young tableau. When |σ|=1, the time required by the algorithm is improved to O(n log k). When |σ|=2, the time required by the algorithm is improved to O(n), an optimal algorithm.