{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,13]],"date-time":"2026-02-13T23:19:09Z","timestamp":1771024749541,"version":"3.50.1"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319238258","type":"print"},{"value":"9783319238265","type":"electronic"}],"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-23826-5_18","type":"book-chapter","created":{"date-parts":[[2015,9,4]],"date-time":"2015-09-04T08:20:20Z","timestamp":1441354820000},"page":"177-187","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Filtration Algorithms for Approximate Order-Preserving Matching"],"prefix":"10.1007","author":[{"given":"Tamanna","family":"Chhabra","sequence":"first","affiliation":[]},{"given":"Emanuele","family":"Giaquinta","sequence":"additional","affiliation":[]},{"given":"Jorma","family":"Tarhio","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,5]]},"reference":[{"key":"18_CR1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"66","DOI":"10.1007\/978-3-642-45030-3_7","volume-title":"Algorithms and Computation","author":"D Belazzougui","year":"2013","unstructured":"Belazzougui, D., Pierrot, A., Raffinot, M., Vialette, S.: Single and multiple consecutive permutation motif search. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. LNCS, vol. 8283, pp. 66\u201377. Springer, Heidelberg (2013)"},{"issue":"4\/5","key":"18_CR2","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/BF01185431","volume":"12","author":"WI Chang","year":"1994","unstructured":"Chang, W.I., Lawler, E.L.: Sublinear approximate string matching and biological applications. Algorithmica 12(4\/5), 327\u2013344 (1994)","journal-title":"Algorithmica"},{"key":"18_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-3-319-07959-2_26","volume-title":"Experimental Algorithms","author":"T Chhabra","year":"2014","unstructured":"Chhabra, T., Tarhio, J.: Order-preserving matching with filtration. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 307\u2013314. Springer, Heidelberg (2014)"},{"issue":"2","key":"18_CR4","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1016\/j.ipl.2014.10.018","volume":"115","author":"S Cho","year":"2015","unstructured":"Cho, S., Na, J.C., Park, K., Sim, J.S.: A fast algorithm for order-preserving pattern matching. Inf. Process. Lett. 115(2), 397\u2013402 (2015)","journal-title":"Inf. Process. Lett."},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1007\/978-3-319-02432-5_13","volume-title":"String Processing and Information Retrieval","author":"M Crochemore","year":"2013","unstructured":"Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Kubica, M., Langiu, A., Pissis, S.P., Radoszewski, J., Rytter, W., Wale\u0144, T.: Order-preserving incomplete suffix trees and order-preserving indexes. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) SPIRE 2013. LNCS, vol. 8214, pp. 84\u201395. Springer, Heidelberg (2013)"},{"key":"18_CR6","unstructured":"Gawrychowski, P., Uznanski, P.: Order-preserving pattern matching with k mismatches. CoRR, abs\/1309.6453 (2013)"},{"key":"18_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/978-3-319-07566-2_14","volume-title":"Combinatorial Pattern Matching","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Uzna\u0144ski, P.: Order-preserving pattern matching with k mismatches. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) CPM 2014. LNCS, vol. 8486, pp. 130\u2013139. Springer, Heidelberg (2014)"},{"issue":"19\u201321","key":"18_CR8","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.ipl.2013.07.002","volume":"113","author":"E Giaquinta","year":"2013","unstructured":"Giaquinta, E., Grabowski, S., Fredriksson, K.: Approximate pattern matching with k-mismatches in packed text. Inf. Process. Lett. 113(19\u201321), 693\u2013697 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"18_CR9","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.jalgor.2003.09.001","volume":"50","author":"Y Han","year":"2004","unstructured":"Han, Y.: Deterministic sorting in $${O}(n\\log \\log n)$$ time and linear space. J. Algorithms 50(1), 96\u2013105 (2004)","journal-title":"J. Algorithms"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"315","DOI":"10.1007\/978-3-319-07959-2_27","volume-title":"Experimental Algorithms","author":"T Hirvola","year":"2014","unstructured":"Hirvola, T., Tarhio, J.: Approximate online matching of circular strings. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 315\u2013325. Springer, Heidelberg (2014)"},{"issue":"6","key":"18_CR11","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1002\/spe.4380100608","volume":"10","author":"RN Horspool","year":"1980","unstructured":"Horspool, R.N.: Practical fast searching in strings. Softw. Pract. Exper. 10(6), 501\u2013506 (1980)","journal-title":"Softw. Pract. Exper."},{"issue":"11","key":"18_CR12","doi-asserted-by":"publisher","first-page":"1221","DOI":"10.1002\/spe.4380211105","volume":"21","author":"A Hume","year":"1991","unstructured":"Hume, A., Sunday, D.: Fast string searching. Softw. Pract. Exper. 21(11), 1221\u20131248 (1991)","journal-title":"Softw. Pract. Exper."},{"key":"18_CR13","doi-asserted-by":"crossref","unstructured":"Jacobson, G., Vo, K.: Heaviest increasing\/common subsequence problems. In: Proceedings of the Combinatorial Pattern Matching, Third Annual Symposium, CPM 1992, Tucson, Arizona, USA, April 29\u2013May 1, pp. 52\u201366 (1992)","DOI":"10.1007\/3-540-56024-6_5"},{"key":"18_CR14","doi-asserted-by":"publisher","first-page":"68","DOI":"10.1016\/j.tcs.2013.10.006","volume":"525","author":"J Kim","year":"2014","unstructured":"Kim, J., Eades, P., Fleischer, R., Hong, S., Iliopoulos, C.S., Park, K., Puglisi, S.J., Tokuyama, T.: Order-preserving matching. Theor. Comput. Sci. 525, 68\u201379 (2014)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"18_CR15","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth Jr","year":"1977","unstructured":"Knuth Jr., D.E., Morris, J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"12","key":"18_CR16","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1016\/j.ipl.2013.03.015","volume":"113","author":"M Kubica","year":"2013","unstructured":"Kubica, M., Kulczynski, T., Radoszewski, J., Rytter, W., Walen, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett. 113(12), 430\u2013433 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"13","key":"18_CR17","doi-asserted-by":"publisher","first-page":"1265","DOI":"10.1002\/spe.411","volume":"31","author":"G Navarro","year":"2001","unstructured":"Navarro, G.: Nr-grep: a fast and flexible pattern-matching tool. Softw. Pract. Exper. 31(13), 1265\u20131312 (2001)","journal-title":"Softw. Pract. Exper."},{"key":"18_CR18","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/351827.384246","volume":"5","author":"G Navarro","year":"2000","unstructured":"Navarro, G., Raffinot, M.: Fast and flexible string matching by combining bit-parallelism and suffix automata. ACM Journal of Experimental Algorithmics 5, 4 (2000)","journal-title":"ACM Journal of Experimental Algorithmics"},{"key":"18_CR19","doi-asserted-by":"crossref","unstructured":"Peltola, H., Tarhio, J.: Alternative algorithms for bit-parallel string matching. In: Proceedings of the String Processing and Information Retrieval, 10th International Symposium, SPIRE 2003, Manaus, Brazil, October 8\u201310, pp. 80\u201394 (2003)","DOI":"10.1007\/978-3-540-39984-1_7"},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1007\/978-3-540-68552-4_12","volume-title":"Experimental Algorithms","author":"S Vigna","year":"2008","unstructured":"Vigna, S.: Broadword implementation of rank\/select queries. In: McGeoch, C.C. (ed.) WEA 2008. LNCS, vol. 5038, pp. 154\u2013168. Springer, Heidelberg (2008)"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-23826-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,24]],"date-time":"2023-01-24T13:32:08Z","timestamp":1674567128000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-23826-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783319238258","9783319238265"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-23826-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015]]},"assertion":[{"value":"5 September 2015","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}