Shufen Kuo and George R. Cross, "A Two-Step String Matching Procedure," Pattern Recognition, 24(7), 711-716, 1991.

Abstract: String-matching algorithms which will be used as part of a knowledge-based retrieval system for multimedia documents consisting of the graphical images of corporate trademarks, trademark words or phrases, and representations of companies and products are discussed. Let LLCS(A,B) denote the length of the longest common subsequence of two strings A and B. We describe an improvement to the Wagner-Fischer Algorithm called WF+ for finding the LLCS which runs in linear space and quadratic time. An approximate algorithm for finding the LLCS, called the sorted string approximate algorithm (SSAA) is then presented, which runs in linear time but works on strings in sorted order only. The SSAA and WF+ are then combined into a two-step matching procedure which retrieves strings similar to a given string in near-linear time. Emprirical data are presented in support of the estimate of average running time for the algorithm.