Longest k-distance substrings of two strings
János Csirik, Horst Bunke · 2003
A feature vector is introduced for measuring pattern similarities between two strings. The following problem is solved: Given strings A and B and a distance d, let the distance between A and B be D=d(A,B). Then, for r=0, 1, 2 . . . D determine substrings I and J of A and B, respectively, such that the sum of the length of I and J is maximum and the distance between I and J is maximum and the distance between I and J is equal to r, i.e. d(I,J)=r. The algorithm used to solve this problem has a time complexity of O(n/sup 2/m/sup 2/).>