A polynomial‐time algorithm for computing characteristic strings under a set of strings
Minoru Ito, Kuniyasu Shimizu, Michio Nakanishi, Akihiro Hashimoto · Systems and Computers in Japan · 1995
Abstract A substring of a string a1a2…an has the form ai+1ai+2…aj. The difference between two strings is the minimum number of editing 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 δ be a positive integer. A δ‐characteristic string of T under S is a string that is a common substring of T and that has at least δ‐differences from any substring of any string in S ‐ T. In this paper, the following result is presented. It can be decided in O(l2 · S) time whether or not there exists a δ‐characteristic string of T under S, where l 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 δ‐characteristic strings of T under S can also be obtained in that time.