An improved algorithm to find the length of the longest common subsequence of two strings

Abstract

Let A and B be strings of common length n. Define LLCS ( A, B ) to be the length of the longest common subsequence of A and B. Hunt and Szymanski presented an algorithm for finding LLCS ( A, B ) with time complexity O (( r + n ) logn ), where r is the number of elements in the set {( i, j )| A [ i ] = B [ j ]}. In the worst case the algorithm has running time of O ( n 2 logn ). We present an improvement to this algorithm which changes the time complexity to O ( r + n ( LLCS ( A, B ) + logn )). Some experimental results show dramatic improvements for large n.