Name
Abstract | ||
|---|---|---|
The difference between two strings is the minimum number of editing steps (insertions, deletions, changes) that convert 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.lt can be decided in O(T+l
2 · ¦S– T¦+l ··¦¦S–T¦¦) time whether or not there exists a -characteristic string of T under S, where l denotes the length of a shortest string in T, ¦S– T¦ the cardinality of S – T, and T the size of T. If such a string exits, then all the shortest -characteristic strings of T under S can also be obtained in that time. |
Year | DOI | Venue |
|---|---|---|
1994 | 10.1007/3-540-58094-8_24 | CPM |
Keywords | Field | DocType |
approximate pattern matching,characteristic string,dna probe,polynomial-time algorithms,computing characteristic strings | Integer,Discrete mathematics,Substring,Combinatorics,Finite set,Existential quantification,Cardinality,Approximate string matching,Time complexity,Mathematics | Conference |
ISBN | Citations | PageRank |
3-540-58094-8 | 8 | 1.44 |
References | Authors | |
11 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Minoru Ito | 1 | 483 | 77.61 |
| Kuniyasu Shimizu | 2 | 12 | 5.77 |
| Michio Nakanishi | 3 | 34 | 11.90 |
| Akihiro Hashimoto | 4 | 408 | 153.74 |