{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T05:40:58Z","timestamp":1698298858880},"reference-count":14,"publisher":"Wiley","issue":"3","license":[{"start":{"date-parts":[[2007,3,21]],"date-time":"2007-03-21T00:00:00Z","timestamp":1174435200000},"content-version":"vor","delay-in-days":4462,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Systems &amp; Computers in Japan"],"published-print":{"date-parts":[[1995,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A substring of a string <jats:italic>a<\/jats:italic><jats:sub>1<\/jats:sub><jats:italic>a<\/jats:italic><jats:sub>2<\/jats:sub>\u2026<jats:italic>a<\/jats:italic><jats:sub>n<\/jats:sub> has the form <jats:italic>a<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic>+1<\/jats:sub><jats:italic>a<\/jats:italic><jats:sub><jats:italic>i<\/jats:italic>+2<\/jats:sub>\u2026<jats:italic>a<\/jats:italic><jats:sub><jats:italic>j<\/jats:italic><\/jats:sub>. The difference between two strings is the minimum number of editing steps (insertions, deletions, changes) that transform one string into the other. Let <jats:italic>S<\/jats:italic> be a finite set of strings, let <jats:italic>T<\/jats:italic> be a subset of <jats:italic>S<\/jats:italic>, and let \u03b4 be a positive integer. A \u03b4\u2010characteristic string of <jats:italic>T<\/jats:italic> under <jats:italic>S<\/jats:italic> is a string that is a common substring of <jats:italic>T<\/jats:italic> and that has at least \u03b4\u2010differences from any substring of any string in <jats:italic>S \u2010 T<\/jats:italic>.<\/jats:p><jats:p>In this paper, the following result is presented. It can be decided in <jats:italic>O<\/jats:italic>(<jats:italic>l<\/jats:italic><jats:sup>2<\/jats:sup> \u00b7 <jats:italic>S<\/jats:italic>) time whether or not there exists a \u03b4\u2010characteristic string of <jats:italic>T<\/jats:italic> under <jats:italic>S<\/jats:italic>, where <jats:italic>l<\/jats:italic> is the length of a shortest string in <jats:italic>T<\/jats:italic>, and <jats:italic>S<\/jats:italic> is the size of <jats:italic>S<\/jats:italic>. If such a string exists, then all the shortest \u03b4\u2010characteristic strings of <jats:italic>T<\/jats:italic> under <jats:italic>S<\/jats:italic> can also be obtained in that time.<\/jats:p>","DOI":"10.1002\/scj.4690260303","type":"journal-article","created":{"date-parts":[[2007,7,8]],"date-time":"2007-07-08T08:16:54Z","timestamp":1183882614000},"page":"30-38","source":"Crossref","is-referenced-by-count":1,"title":["A polynomial\u2010time algorithm for computing characteristic strings under a set of strings"],"prefix":"10.1002","volume":"26","author":[{"given":"Minoru","family":"Ito","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kuniyasu","family":"Shimizu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michio","family":"Nakanishi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akihiro","family":"Hashimoto","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2007,3,21]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/359842.359859"},{"issue":"5","key":"e_1_2_1_3_2","doi-asserted-by":"crossref","first-page":"1068","DOI":"10.1128\/jcm.26.5.1068-1069.1988","article-title":"Comparison of gene\u2010probe commercial kit and culture technique for the diagnosis of mycoplasma pneumoniae infection","volume":"26","author":"Dular R.","year":"1988","journal-title":"Journal of Clinical Microbiology"},{"issue":"2","key":"e_1_2_1_4_2","first-page":"151","article-title":"Fast and sensitive multiple sequence alignments on a microcomputer","volume":"5","author":"Higgins D. G.","year":"1989","journal-title":"CABIOS"},{"key":"e_1_2_1_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/0206024"},{"key":"e_1_2_1_6_2","doi-asserted-by":"crossref","unstructured":"G. M.LandauandU.Vishkin.Introducing efficient parallelism into approximate string matching and a new serial algorithm. Proc. 18th ACM Symp. on Theory of Computing pp.220\u2013230(May1986).","DOI":"10.1145\/12130.12152"},{"key":"e_1_2_1_7_2","volume-title":"Gene Probe for Bacteria","author":"Macario A. J.","year":"1990"},{"key":"e_1_2_1_8_2","doi-asserted-by":"crossref","unstructured":"M.Nakanishi M.Hasidume M.ItoandA.Hashimoto.A linear\u2010time algorithm for computing characteristic strings. Proc. 5th Int. Symp. on Algorithms and Computation Lecture Notes in Computer Science 834 pp.315\u2013323(Aug.1994).","DOI":"10.1007\/3-540-58325-4_195"},{"key":"e_1_2_1_9_2","unstructured":"M.Nasu K.Shimada S.Inaoka K.TaniandM.Kondo.Natural bacterial populations in river water determined by 16S and 23S rRNA\u2010targeted oligonucleotide probes. (submitted to Biomedial and Environmental Sciences)."},{"key":"e_1_2_1_10_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.85.8.2444"},{"key":"e_1_2_1_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(80)90016-4"},{"key":"e_1_2_1_12_2","doi-asserted-by":"crossref","unstructured":"E.Ukkonen.On approximate string matching. Proc. Int. Conf. on Foundations of Computation Theory Lecture Notes on Computer Science158 pp.487\u2013495(Aug.1983).","DOI":"10.1007\/3-540-12689-9_129"},{"key":"e_1_2_1_13_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90023-9"},{"key":"e_1_2_1_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(85)80046-2"},{"key":"e_1_2_1_15_2","doi-asserted-by":"crossref","unstructured":"Science 1991 254 Genome Databases","DOI":"10.1126\/science.1925577"}],"container-title":["Systems and Computers in Japan"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fscj.4690260303","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/scj.4690260303","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T01:48:58Z","timestamp":1698284938000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/scj.4690260303"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1995,1]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[1995,1]]}},"alternative-id":["10.1002\/scj.4690260303"],"URL":"https:\/\/doi.org\/10.1002\/scj.4690260303","archive":["Portico"],"relation":{},"ISSN":["0882-1666","1520-684X"],"issn-type":[{"value":"0882-1666","type":"print"},{"value":"1520-684X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1995,1]]}}}