A POLYNOMIAL-TIME ALGORITHM FOR COMPUTING CHARACTERISTIC STRINGS UNDER A SET OF STRINGS

A substring of a string a(1)a(2) ... a(n) has the form a(i+1)a(i+2)... a(j). The difference between two strings is the minimum number of edi ting steps (insertions, deletions, changes) that transform one string into the other. Let S be a finite set of strings, let T be a subset of S, and let S be a positive integer. A delta-characteristic string of T under S is a string that is a common substring of T and that has at least S-differences from any substring of any string in S - T. In this paper, the following result is presented. It can be decided in O(l(2) .\\S\\) time whether or not there exists. a delta-characteristic stri ng of T under S, where I is the length of a shortest string in T, and \\S\\ is the size of S. If such a string exists, then all the shortest delta-characteristic strings of T under S can also be obtained in tha t time.