{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T03:44:28Z","timestamp":1743047068816,"version":"3.40.3"},"publisher-location":"Cham","reference-count":25,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319193144"},{"type":"electronic","value":"9783319193151"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-319-19315-1_5","type":"book-chapter","created":{"date-parts":[[2015,6,6]],"date-time":"2015-06-06T10:42:08Z","timestamp":1433587328000},"page":"49-61","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Fast and Simple Computations Using Prefix Tables Under Hamming and Edit Distance"],"prefix":"10.1007","author":[{"given":"Carl","family":"Barton","sequence":"first","affiliation":[]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"given":"William F.","family":"Smyth","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,6,7]]},"reference":[{"issue":"6","key":"5_CR1","doi-asserted-by":"publisher","first-page":"1039","DOI":"10.1137\/0216067","volume":"16","author":"K Abrahamson","year":"1987","unstructured":"Abrahamson, K.: Generalized string matching. SIAM J. Comput. 16(6), 1039\u20131051 (1987)","journal-title":"SIAM J. Comput."},{"key":"5_CR2","unstructured":"Amir, A., Lewenstein, M., Porat, E.: Faster algorithms for string matching with $$k$$ mismatches. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2000), pp. 794\u2013803. Society for Industrial and Applied Mathematics, USA (2000)"},{"key":"5_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-642-45278-9_5","volume-title":"Combinatorial Algorithms","author":"W Bland","year":"2013","unstructured":"Bland, W., Kucherov, G., Smyth, W.F.: Prefix table construction and conversion. In: Lecroq, T., Mouchard, L. (eds.) IWOCA 2013. LNCS, vol. 8288, pp. 41\u201353. Springer, Heidelberg (2013)"},{"key":"5_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, New York (2007)"},{"issue":"2","key":"5_CR5","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1016\/j.ipl.2005.11.019","volume":"98","author":"S Dori","year":"2006","unstructured":"Dori, S., Landau, G.M.: Construction of Aho Corasick automaton in linear time for integer alphabets. Inf. Process. Lett. 98(2), 66\u201372 (2006)","journal-title":"Inf. Process. Lett."},{"key":"5_CR6","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)"},{"issue":"2","key":"5_CR7","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1137\/090779759","volume":"40","author":"J Fischer","year":"2011","unstructured":"Fischer, J., Heun, V.: Space-efficient preprocessing schemes for range minimum queries on static arrays. SIAM J. Comput. 40(2), 465\u2013492 (2011)","journal-title":"SIAM J. Comput."},{"key":"5_CR8","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1005813.1041513","volume":"9","author":"K Fredriksson","year":"2004","unstructured":"Fredriksson, K., Navarro, G.: Average-optimal single and multiple approximate string matching. J. Exp. Algorithmics 9, 1\u201347 (2004). http:\/\/doi.acm.org\/10.1145\/1005813.1041513","journal-title":"J. Exp. Algorithmics"},{"issue":"4","key":"5_CR9","doi-asserted-by":"publisher","first-page":"52","DOI":"10.1145\/8307.8309","volume":"17","author":"Z Galil","year":"1986","unstructured":"Galil, Z., Giancarlo, R.: Improved string matching with $$k$$ mismatches. ACM SIGACT News 17(4), 52\u201354 (1986)","journal-title":"ACM SIGACT News"},{"key":"5_CR10","volume-title":"Higher Algebra","author":"HS Hall","year":"1950","unstructured":"Hall, H.S., Knight, S.R.: Higher Algebra. MacMillan, London (1950)"},{"key":"5_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1084","DOI":"10.1007\/978-3-642-10631-6_109","volume-title":"Algorithms and Computation","author":"P-H Hsu","year":"2009","unstructured":"Hsu, P.-H., Chen, K.-Y., Chao, K.-M.: Finding all approximate gapped palindromes. In: Dong, Y., Du, D.-Z., Ibarra, O. (eds.) ISAAC 2009. LNCS, vol. 5878, pp. 1084\u20131093. Springer, Heidelberg (2009). http:\/\/dx.doi.org\/10.1007\/3-540-12689-9_129"},{"issue":"4","key":"5_CR12","doi-asserted-by":"publisher","first-page":"418","DOI":"10.1016\/j.jda.2010.08.004","volume":"8","author":"L Ilie","year":"2010","unstructured":"Ilie, L., Navarro, G., Tinta, L.: The longest common extension problem revisited and applications to approximate string searching. J. Discrete Algorithms 8(4), 418\u2013428 (2010)","journal-title":"J. Discrete Algorithms"},{"key":"5_CR13","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1137\/S0097539794264810","volume":"27\u20132","author":"GM Landau","year":"1998","unstructured":"Landau, G.M., Myers, E.W., Schmidt, J.P.: Incremental string comparison. SIAM J. Comput. 27\u20132, 557\u2013582 (1998)","journal-title":"SIAM J. Comput."},{"key":"5_CR14","doi-asserted-by":"crossref","unstructured":"Landau, G.M., Vishkin, U.: Efficient string matching in the presence of errors. In: IEEE (ed.) Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), USA, pp. 126\u2013136. IEEE Computer Society (1985)","DOI":"10.1109\/SFCS.1985.22"},{"key":"5_CR15","unstructured":"Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions, and reversals. Technical report 8 (1966)"},{"key":"5_CR16","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"MG Main","year":"1984","unstructured":"Main, M.G., Lorentz, R.J.: An $$\\cal O$$(n log n) algorithm for finding all repetitions in a string. J. Algs 5, 422\u2013432 (1984)","journal-title":"J. Algs"},{"key":"5_CR17","doi-asserted-by":"crossref","unstructured":"Nong, G., Zhang, S., Chan, W.H.: Linear suffix array construction by almost pure induced-sorting. In: Proceedings of the 2009 Data Compression Conference, DCC 2009, pp. 193\u2013202, IEEE Computer Society, Washington, DC (2009)","DOI":"10.1109\/DCC.2009.42"},{"key":"5_CR18","unstructured":"Pizza & Chili, April 2013. http:\/\/pizzachili.dcc.uchile.cl\/"},{"key":"5_CR19","volume-title":"Computing Patterns in Strings","author":"B Smyth","year":"2003","unstructured":"Smyth, B.: Computing Patterns in Strings. Pearson Addison-Wesley, London (2003)"},{"key":"5_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/978-3-540-89097-3_14","volume-title":"String Processing and Information Retrieval","author":"WF Smyth","year":"2008","unstructured":"Smyth, W.F., Wang, S.: New perspectives on the prefix array. In: Amir, A., Turpin, A., Moffat, A. (eds.) SPIRE 2008. LNCS, vol. 5280, pp. 133\u2013143. Springer, Heidelberg (2008)"},{"key":"5_CR21","unstructured":"StringPedia, April 2013. http:\/\/stringpedia.bsmithers.co.uk"},{"key":"5_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1007\/3-540-12689-9_129","volume-title":"Foundations of Computation Theory","author":"E Ukkonen","year":"1983","unstructured":"Ukkonen, E.: On approximate string matching. In: Karpinski, M. (ed.) Foundations of Computation Theory. Lecture Notes in Computer Science, vol. 158, pp. 487\u2013495. Springer, Heidelberg (1983). http:\/\/dx.doi.org\/10.1007\/3-540-12689-9_129"},{"key":"5_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-13509-5_8","volume-title":"Combinatorial Pattern Matching","author":"N V\u00e4lim\u00e4ki","year":"2010","unstructured":"V\u00e4lim\u00e4ki, N., Ladra, S., M\u00e4kinen, V.: Approximate all-pairs suffix\/prefix overlaps. In: Amir, A., Parida, L. (eds.) CPM 2010. LNCS, vol. 6129, pp. 76\u201387. Springer, Heidelberg (2010)"},{"issue":"10","key":"5_CR24","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1145\/135239.135244","volume":"35","author":"S Wu","year":"1992","unstructured":"Wu, S., Manber, U.: Fast text searching: allowing errors. Commun. ACM 35(10), 83\u201391 (1992)","journal-title":"Commun. ACM"},{"issue":"5","key":"5_CR25","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1093\/bioinformatics\/btt593","volume":"30","author":"J Zhang","year":"2013","unstructured":"Zhang, J., Kobert, K., Flouri, T., Stamatakis, A.: PEAR: a fast and accurate Illumina paired-end reAd mergeR. Bioinformatics 30(5), 614\u2013620 (2013)","journal-title":"Bioinformatics"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-19315-1_5","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,20]],"date-time":"2023-01-20T09:11:20Z","timestamp":1674205880000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-19315-1_5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319193144","9783319193151"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-19315-1_5","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"7 June 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}