{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T15:37:02Z","timestamp":1725550622318},"publisher-location":"Berlin, Heidelberg","reference-count":19,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540297406"},{"type":"electronic","value":"9783540322412"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2005]]},"DOI":"10.1007\/11575832_29","type":"book-chapter","created":{"date-parts":[[2005,10,13]],"date-time":"2005-10-13T14:12:50Z","timestamp":1129212770000},"page":"256-266","source":"Crossref","is-referenced-by-count":1,"title":["Restricted Transposition Invariant Approximate String Matching Under Edit Distance"],"prefix":"10.1007","author":[{"given":"Heikki","family":"Hyyr\u00f6","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"29_CR1","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01185431","volume":"12","author":"W.I. Chang","year":"1994","unstructured":"Chang, W.I., Lawler, E.L.: Sublinear approximate string matching and biological applications. Algorithmica\u00a012, 327\u2013344 (1994)","journal-title":"Algorithmica"},{"issue":"3","key":"29_CR2","doi-asserted-by":"publisher","first-page":"519","DOI":"10.1145\/146637.146650","volume":"39","author":"D. Eppstein","year":"1992","unstructured":"Eppstein, D., Galil, Z., Giancarlo, R., Italiano, G.F.: Sparse dynamic programming I: linear cost functions. Journal of ACM\u00a039(3), 519\u2013545 (1992)","journal-title":"Journal of ACM"},{"key":"29_CR3","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Bentley, J.L., Tarjan, R.E.: Scaling and related techniques for geometry problems. In: Proc. 16th ACM Symposium on Theory of Computing (STOC 1984), pp. 135\u2013143 (1984)","DOI":"10.1145\/800057.808675"},{"key":"29_CR4","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/0304-3975(92)90135-3","volume":"92","author":"Z. Galil","year":"1992","unstructured":"Galil, Z., Park, K.: Dynamic programming with convexity, concavity and sparsity. Theoretical Computer Science\u00a092, 49\u201376 (1992)","journal-title":"Theoretical Computer Science"},{"key":"29_CR5","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1145\/322033.322044","volume":"24","author":"D.S. Hirschberg","year":"1977","unstructured":"Hirschberg, D.S.: Algorithms for the longest common subsequence problem. Journal of ACM\u00a024, 664\u2013675 (1977)","journal-title":"Journal of ACM"},{"key":"29_CR6","doi-asserted-by":"publisher","first-page":"295","DOI":"10.1007\/BF01786986","volume":"15","author":"D.B. Johnson","year":"1982","unstructured":"Johnson, D.B.: A priority queue in which initialization and queue operations take O(loglog D) time. Mathematical Systems Theory\u00a015, 295\u2013309 (1982)","journal-title":"Mathematical Systems Theory"},{"issue":"12","key":"29_CR7","doi-asserted-by":"publisher","first-page":"1439","DOI":"10.1002\/(SICI)1097-024X(199612)26:12<1439::AID-SPE71>3.0.CO;2-1","volume":"26","author":"P. Jokinen","year":"1996","unstructured":"Jokinen, P., Tarhio, J., Ukkonen, E.: A comparison of approximate string matching algorithms. Software Practice & Experience\u00a026(12), 1439\u20131458 (1996)","journal-title":"Software Practice & Experience"},{"key":"29_CR8","unstructured":"Lemstr\u00f6m, K., Ukkonen, E.: Including interval encoding into edit distance based music comparison and retrieval. In: Proc. Symposium on Creative & Cultural Aspects and Applications of AI & Cognitive Science (AISB 2000), pp. 53\u201360 (2000)"},{"key":"29_CR9","doi-asserted-by":"crossref","unstructured":"Lemstr\u00f6m, K., Navarro, G., Pinzon, Y.: Practical algorithms for transposition-invariant string-matching. Journal of Discrete Algorithms (to appear)","DOI":"10.1016\/j.jda.2004.08.009"},{"key":"29_CR10","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1016\/0196-6774(89)90010-2","volume":"10","author":"G.M. Landau","year":"1989","unstructured":"Landau, G.M., Vishkin, U.: Fast parallel and serial approximate string matching. Journal of Algorithms\u00a010, 157\u2013169 (1989)","journal-title":"Journal of Algorithms"},{"key":"29_CR11","first-page":"12","volume":"1","author":"V.I. Levenshtein","year":"1965","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting spurious insertions and deletions of ones (original in Russian). Russian Problemy Peredachi Informatsii\u00a01, 12\u201325 (1965)","journal-title":"Russian Problemy Peredachi Informatsii"},{"key":"29_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/3-540-36494-3_18","volume-title":"STACS 2003","author":"V. M\u00e4kinen","year":"2003","unstructured":"M\u00e4kinen, V., Navarro, G., Ukkonen, E.: Algorithms for transposition invariant string matching. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol.\u00a02607, pp. 191\u2013202. Springer, Heidelberg (2003)"},{"key":"29_CR13","doi-asserted-by":"crossref","unstructured":"M\u00e4kinen, V., Navarro, G., Ukkonen, E.: Transposition invariant string matching. Journal of Algorithms (to appear)","DOI":"10.1016\/j.jalgor.2004.07.008"},{"key":"29_CR14","doi-asserted-by":"crossref","unstructured":"Navarro, G.: Multiple approximate string matching by counting. In: Proc. 4th South American Workshop on String Processing (WSP 1997), pp. 125\u2013139 (1997)","DOI":"10.1515\/9780773591400-012"},{"issue":"1","key":"29_CR15","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/375360.375365","volume":"33","author":"G. Navarro","year":"2001","unstructured":"Navarro, G.: A guided tour to approximate string matching. ACM Computing Surveys\u00a033(1), 31\u201388 (2001)","journal-title":"ACM Computing Surveys"},{"key":"29_CR16","doi-asserted-by":"publisher","first-page":"359","DOI":"10.1016\/0196-6774(80)90016-4","volume":"1","author":"P. Sellers","year":"1980","unstructured":"Sellers, P.: The theory and computation of evolutionary distances: pattern recognition. Journal of Algorithms\u00a01, 359\u2013373 (1980)","journal-title":"Journal of Algorithms"},{"key":"29_CR17","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1016\/S0019-9958(85)80046-2","volume":"64","author":"E. Ukkonen","year":"1985","unstructured":"Ukkonen, E.: Algorithms for approximate string matching. Information and Control\u00a064, 100\u2013118 (1985)","journal-title":"Information and Control"},{"key":"29_CR18","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1016\/0020-0190(77)90031-X","volume":"6","author":"P. Emde Boas van","year":"1977","unstructured":"van Emde Boas, P.: Preserving order in a forest in less than logarithmic time and linear space. Information Processing Letters\u00a06, 80\u201382 (1977)","journal-title":"Information Processing Letters"},{"issue":"1","key":"29_CR19","doi-asserted-by":"publisher","first-page":"168","DOI":"10.1145\/321796.321811","volume":"21","author":"R. Wagner","year":"1974","unstructured":"Wagner, R., Fisher, M.: The string-to-string correction problem. Journal of ACM\u00a021(1), 168\u2013173 (1974)","journal-title":"Journal of ACM"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11575832_29.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,30]],"date-time":"2024-01-30T23:19:51Z","timestamp":1706656791000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11575832_29"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005]]},"ISBN":["9783540297406","9783540322412"],"references-count":19,"URL":"https:\/\/doi.org\/10.1007\/11575832_29","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2005]]}}}