{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:52Z","timestamp":1759638112372},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319731162"},{"type":"electronic","value":"9783319731179"}],"license":[{"start":{"date-parts":[[2017,12,22]],"date-time":"2017-12-22T00:00:00Z","timestamp":1513900800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2018]]},"DOI":"10.1007\/978-3-319-73117-9_45","type":"book-chapter","created":{"date-parts":[[2017,12,21]],"date-time":"2017-12-21T16:45:34Z","timestamp":1513874734000},"page":"636-649","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Longest Common Prefixes with k-Mismatches and Applications"],"prefix":"10.1007","author":[{"given":"Hayam","family":"Alamro","sequence":"first","affiliation":[]},{"given":"Lorraine A. K.","family":"Ayad","sequence":"additional","affiliation":[]},{"given":"Panagiotis","family":"Charalampopoulos","sequence":"additional","affiliation":[]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,12,22]]},"reference":[{"issue":"1","key":"45_CR1","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discret. Algorithms 2(1), 53\u201386 (2004)","journal-title":"J. Discret. Algorithms"},{"issue":"3","key":"45_CR2","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1016\/S0022-2836(05)80360-2","volume":"215","author":"SF Altschul","year":"1990","unstructured":"Altschul, S.F., Gish, W., Miller, W., Myers, E.W., Lipman, D.J.: Basic local alignment search tool. J. Mol. Biol. 215(3), 403\u2013410 (1990)","journal-title":"J. Mol. Biol."},{"key":"45_CR3","doi-asserted-by":"publisher","unstructured":"Alzamel, M., Charalampopoulos, P., Iliopoulos, C.S., Pissis, S.P., Radoszewski, J., Sung, W.-K.: Faster algorithms for 1-mappability of a sequence. In: COCOA. LNCS, vol. 10628, pp. 109\u2013121. Springer International Publishing (2017). https:\/\/doi.org\/10.1007\/978-3-319-71147-8_8","DOI":"10.1007\/978-3-319-71147-8_8"},{"issue":"2","key":"45_CR4","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/1240233.1240242","volume":"3","author":"A Amir","year":"2007","unstructured":"Amir, A., Landau, G.M., Lewenstein, M., Sokol, D.: Dynamic text and static pattern matching. ACM Trans. Algorrithms 3(2), 19 (2007)","journal-title":"ACM Trans. Algorrithms"},{"key":"45_CR5","doi-asserted-by":"crossref","unstructured":"Antoniou, P., Daykin, J.W., Iliopoulos, C.S., Kourie, D., Mouchard, L., Pissis, S.P.: Mapping uniquely occurring short sequences derived from high throughput technologies to a reference genome. In: ITAB, pp. 1\u20134. IEEE Computer Society (2009)","DOI":"10.1109\/ITAB.2009.5394394"},{"key":"45_CR6","unstructured":"Barthet, M., Plumbley, M.D., Kachkaev, A., Dykes, J., Wolff, D., Weyde, T.: Big chord data extraction and mining. In: CIM (2014)"},{"key":"45_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"88","DOI":"10.1007\/10719839_9","volume-title":"LATIN 2000: Theoretical Informatics","author":"MA Bender","year":"2000","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: Gonnet, G.H., Viola, A. (eds.) LATIN 2000. LNCS, vol. 1776, pp. 88\u201394. Springer, Heidelberg (2000). https:\/\/doi.org\/10.1007\/10719839_9"},{"key":"45_CR8","volume-title":"Understandable Guide to Music Theory: The Most Useful Aspects of Theory for Rock, Jazz, and Blues Musicians","author":"C Bufe","year":"1994","unstructured":"Bufe, C.: Understandable Guide to Music Theory: The Most Useful Aspects of Theory for Rock, Jazz, and Blues Musicians. See Sharp Press, Tucson (1994)"},{"key":"45_CR9","doi-asserted-by":"crossref","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC 2004, pp. 91\u2013100. ACM (2004)","DOI":"10.1145\/1007352.1007374"},{"issue":"1","key":"45_CR10","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1016\/j.ejc.2012.07.011","volume":"34","author":"M Crochemore","year":"2013","unstructured":"Crochemore, M., Ilie, L., Iliopoulos, C.S., Kubica, M., Rytter, W., Wale\u0144, T.: Computing the longest previous factor. Eur. J. Comb. 34(1), 15\u201326 (2013)","journal-title":"Eur. J. Comb."},{"key":"45_CR11","doi-asserted-by":"crossref","unstructured":"Crochemore, M., Ilie, L., Smyth, W.F.: A simple algorithm for computing the Lempel Ziv factorization. In: DCC, pp. 482\u2013488. IEEE Computer Society (2008)","DOI":"10.1109\/DCC.2008.36"},{"issue":"1","key":"45_CR12","doi-asserted-by":"crossref","first-page":"e30377","DOI":"10.1371\/journal.pone.0030377","volume":"7","author":"T Derrien","year":"2012","unstructured":"Derrien, T., Estell\u00e9, J., Sola, S.M., Knowles, D., Raineri, E., Guig\u00f3, R., Ribeca, P.: Fast computation and applications of genome mappability. PLoS ONE 7(1), e30377 (2012)","journal-title":"PLoS ONE"},{"key":"45_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"374","DOI":"10.1007\/978-3-642-22300-6_32","volume-title":"Algorithms and Data Structures","author":"J Fischer","year":"2011","unstructured":"Fischer, J.: Inducing the LCP-array. In: Dehne, F., Iacono, J., Sack, J.-R. (eds.) WADS 2011. LNCS, vol. 6844, pp. 374\u2013385. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22300-6_32"},{"key":"45_CR14","unstructured":"Fischer, J., K\u00f6ppl, D., Kurpicz, F.: On the benefit of merging suffix array intervals for parallel pattern matching. In: CPM 2016. LIPIcs, vol. 54, pp. 26:1\u201326:11. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)"},{"issue":"24","key":"45_CR15","doi-asserted-by":"crossref","first-page":"3169","DOI":"10.1093\/bioinformatics\/bts605","volume":"28","author":"NA Fonseca","year":"2012","unstructured":"Fonseca, N.A., Rung, J., Brazma, A., Marioni, J.C.: Tools for mapping high-throughput sequencing data. Bioinformatics 28(24), 3169\u20133177 (2012)","journal-title":"Bioinformatics"},{"issue":"6\u20138","key":"45_CR16","doi-asserted-by":"crossref","first-page":"640","DOI":"10.1016\/j.ipl.2015.03.003","volume":"115","author":"S Grabowski","year":"2015","unstructured":"Grabowski, S.: A note on the longest common substring with $$k$$ k -mismatches problem. Inf. Process. Lett. 115(6\u20138), 640\u2013642 (2015)","journal-title":"Inf. Process. Lett."},{"key":"45_CR17","doi-asserted-by":"crossref","unstructured":"K\u00e4rkk\u00e4inen, J., Kempa, D.: Faster external memory LCP array construction. In: ESA. LIPIcs, vol. 57, pp. 61:1\u201361:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2016)","DOI":"10.1145\/2851491"},{"issue":"18","key":"45_CR18","doi-asserted-by":"crossref","first-page":"5660","DOI":"10.1073\/pnas.80.18.5660","volume":"80","author":"S Karlin","year":"1983","unstructured":"Karlin, S., Ghandour, G., Ost, F., Tavare, S., Korn, L.J.: New approaches for computer analysis of nucleic acid sequences. Proc. Natl. Acad. Sci. U.S.A. 80(18), 5660\u20135664 (1983)","journal-title":"Proc. Natl. Acad. Sci. U.S.A."},{"key":"45_CR19","doi-asserted-by":"crossref","unstructured":"Khmelev, D.V., Teahan, W.J.: A repetition based measure for verification of text collections and for text categorization. In: ACM SIGIR 2003, pp. 104\u2013110. ACM (2003)","DOI":"10.1145\/860435.860456"},{"issue":"13","key":"45_CR20","doi-asserted-by":"crossref","first-page":"3672","DOI":"10.1093\/nar\/gkg617","volume":"31","author":"R Kolpakov","year":"2003","unstructured":"Kolpakov, R., Bana, G., Kucherov, G.: MREPS: efficient and flexible detection of tandem repeats in DNA. Nucleic Acids Res. 31(13), 3672\u20133678 (2003)","journal-title":"Nucleic Acids Res."},{"key":"45_CR21","series-title":"Woodhead Publishing Series in Biomedicine","doi-asserted-by":"crossref","DOI":"10.1533\/9781908818232","volume-title":"Bioinformatics for Biomedical Science and Clinical Applications","author":"K-H Liang","year":"2013","unstructured":"Liang, K.-H.: Bioinformatics for Biomedical Science and Clinical Applications. Woodhead Publishing Series in Biomedicine. Woodhead Publishing, Cambridge (2013)"},{"issue":"5","key":"45_CR22","doi-asserted-by":"crossref","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"45_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-319-23826-5_29","volume-title":"String Processing and Information Retrieval","author":"G Manzini","year":"2015","unstructured":"Manzini, G.: Longest common prefix with mismatches. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 299\u2013310. Springer, Cham (2015). https:\/\/doi.org\/10.1007\/978-3-319-23826-5_29"},{"issue":"11","key":"45_CR24","doi-asserted-by":"crossref","first-page":"1116","DOI":"10.1101\/gr.9.11.1116","volume":"9","author":"C M\u00e9digue","year":"1999","unstructured":"M\u00e9digue, C., Rose, M., Viari, A., Danchin, A.: Detecting and analyzing DNA sequencing errors: toward a higher quality of the bacillus subtilis genome sequence. Genome Res. 9(11), 1116\u20131127 (1999)","journal-title":"Genome Res."},{"issue":"1","key":"45_CR25","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1038\/nrg2626","volume":"11","author":"ML Metzker","year":"2010","unstructured":"Metzker, M.L.: Sequencing technologies - the next generation. Nat. Rev. Genet. 11(1), 31\u201346 (2010)","journal-title":"Nat. Rev. Genet."},{"key":"45_CR26","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure induced-sorting. In: DCC, pp. 193\u2013202. IEEE (2009)","DOI":"10.1109\/DCC.2009.42"},{"issue":"6","key":"45_CR27","doi-asserted-by":"crossref","first-page":"657","DOI":"10.1016\/S0959-437X(99)00031-3","volume":"9","author":"AFA Smit","year":"1999","unstructured":"Smit, A.F.A.: Interspersed repeats and other mementos of transposable elements in mammalian genomes. Curr. Opin. Genet. Dev. 9(6), 657\u2013663 (1999)","journal-title":"Curr. Opin. Genet. Dev."},{"issue":"6","key":"45_CR28","doi-asserted-by":"crossref","first-page":"472","DOI":"10.1089\/cmb.2015.0235","volume":"23","author":"SV Thankachan","year":"2016","unstructured":"Thankachan, S.V., Apostolico, A., Aluru, S.: A provably efficient algorithm for the k-mismatch average common substring problem. J. Comput. Biol. 23(6), 472\u2013482 (2016)","journal-title":"J. Comput. Biol."},{"issue":"6","key":"45_CR29","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1089\/cmb.2015.0217","volume":"23","author":"SV Thankachan","year":"2016","unstructured":"Thankachan, S.V., Chockalingam, S.P., Liu, Y., Apostolico, A., Aluru, S.: ALFRED: a practical method for alignment-free distance computation. J. Comput. Biol. 23(6), 452\u2013460 (2016)","journal-title":"J. Comput. Biol."},{"key":"45_CR30","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: SWAT 1973, pp. 1\u201311. IEEE Computer Society (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2018: Theory and Practice of Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-73117-9_45","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,24]],"date-time":"2020-10-24T17:47:50Z","timestamp":1603561670000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-73117-9_45"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,22]]},"ISBN":["9783319731162","9783319731179"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-73117-9_45","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017,12,22]]}}}