RESIM-an algorithm for finding the similarity of regular expression based patterns and strings
Patrick A. D. Powell · 2003
Searching DNA sequence databases is addressed. An algorithm which finds a similarity measure for both patterns and strings expressed as regular expressions (RE similarity), using only alternation and concatenation, is presented. Given a pattern P with N tokens and depth D, and a string S with length M and depth d, then the RE similarity can be found in O(MN) time and using O(min(M,N)) space. There is a parallel algorithm that performs in O(N+M) time using min(N,M) processors and max(d,D)min(M,N) space. By adding a separator token to the string alphabet, the algorithm can be used to determine the best similarity over all of the delimited strings.>