{"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":1771024749592,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T00:00:00Z","timestamp":1725062400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"Tohoku University Division for International Advanced Research and Education"},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP19K20208"],"award-info":[{"award-number":["JP19K20208"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP18K11150"],"award-info":[{"award-number":["JP18K11150"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["JP15H05706"],"award-info":[{"award-number":["JP15H05706"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002770","name":"Cabinet Office, Government of Japan","doi-asserted-by":"publisher","award":["ImPACT Program of the Council for Science, Technology and Innovation"],"award-info":[{"award-number":["ImPACT Program of the Council for Science, Technology and Innovation"]}],"id":[{"id":"10.13039\/501100002770","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Acta Informatica"],"published-print":{"date-parts":[[2024,12]]},"DOI":"10.1007\/s00236-024-00464-w","type":"journal-article","created":{"date-parts":[[2024,8,31]],"date-time":"2024-08-31T14:01:59Z","timestamp":1725112919000},"page":"415-444","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Serial and parallel algorithms for order-preserving pattern matching based on the duel-and-sweep paradigm"],"prefix":"10.1007","volume":"61","author":[{"given":"Davaajav","family":"Jargalsaikhan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diptarama","family":"Hendrian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yohei","family":"Ueki","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ryo","family":"Yoshinaka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ayumi","family":"Shinohara","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,8,31]]},"reference":[{"key":"464_CR1","unstructured":"Amir, A., Kondratovsky, E.: Sufficient conditions for efficient indexing under different matchings. In: Proceedings of 30th annual symposium on combinatorial pattern matching (CPM 2019), Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)"},{"issue":"2","key":"464_CR2","doi-asserted-by":"publisher","first-page":"313","DOI":"10.1137\/S0097539792226321","volume":"23","author":"A Amir","year":"1994","unstructured":"Amir, A., Benson, G., Farach, M.: An alphabet independent approach to two-dimensional pattern matching. SIAM J. Comput. 23(2), 313\u2013323 (1994)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"464_CR3","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1006\/jagm.1993.1018","volume":"14","author":"O Berkman","year":"1993","unstructured":"Berkman, O., Schieber, B., Vishkin, U.: Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values. J. Algorithms 14(3), 344\u2013370 (1993)","journal-title":"J. Algorithms"},{"issue":"10","key":"464_CR4","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.3598599","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun of the ACM 20(10), 762\u2013772 (1977). https:\/\/doi.org\/10.1145\/359842.3598599","journal-title":"Commun of the ACM"},{"key":"464_CR5","unstructured":"Cantone, D., Faro, S., K\u00fclekci, M.O.: An efficient skip-search approach to the order-preserving pattern matching problem. In: PSC, pp 22\u201335 (2015)"},{"issue":"2","key":"464_CR6","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1016\/j.ipl.2015.10.005","volume":"116","author":"T Chhabra","year":"2016","unstructured":"Chhabra, T., Tarhio, J.: A filtration method for order-preserving matching. Inf. Process. Lett. 116(2), 71\u201374 (2016). https:\/\/doi.org\/10.1016\/j.ipl.2015.10.005","journal-title":"Inf. Process. Lett."},{"key":"464_CR7","doi-asserted-by":"crossref","unstructured":"Chhabra, T., K\u00fclekci, M.O., Tarhio, J.: Alternative algorithms for order-preserving matching. In: PSC, pp 36\u201346 (2015)","DOI":"10.1007\/978-3-319-23826-5_18"},{"issue":"2","key":"464_CR8","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., et al.: A fast algorithm for order-preserving pattern matching. Inf. Process. Lett. 115(2), 397\u2013402 (2015)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"464_CR9","doi-asserted-by":"publisher","first-page":"770","DOI":"10.1137\/0217049","volume":"17","author":"R Cole","year":"1988","unstructured":"Cole, R.: Parallel merge sort. SIAM J. Comput. 17(4), 770\u2013785 (1988)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"464_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2650220","volume":"11","author":"R Cole","year":"2014","unstructured":"Cole, R., Hazay, C., Lewenstein, M., et al.: Two-dimensional parameterized matching. ACM Trans. Algorithms 11(2), 1\u201312 (2014). https:\/\/doi.org\/10.1145\/2650220","journal-title":"ACM Trans. Algorithms"},{"key":"464_CR11","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1016\/j.tcs.2015.06.050","volume":"638","author":"M Crochemore","year":"2016","unstructured":"Crochemore, M., Iliopoulos, C.S., Kociumaka, T., et al.: Order-preserving indexing. Theor. Comput. Sci. 638, 122\u2013135 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2015.06.050","journal-title":"Theor. Comput. Sci."},{"key":"464_CR12","doi-asserted-by":"crossref","unstructured":"Faro, S., K\u00fclekci, M. O.: Efficient algorithms for the order preserving pattern matching problem. In: International Conference on Algorithmic Applications in Management, Springer, pp 185\u2013196 (2016)","DOI":"10.1007\/978-3-319-41168-2_16"},{"issue":"2","key":"464_CR13","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2431211.2431212","volume":"45","author":"S Faro","year":"2013","unstructured":"Faro, S., Lecroq, T.: The exact online string matching problem: a review of the most recent results. ACM Comput. Surv. (CSUR) 45(2), 1\u201342 (2013)","journal-title":"ACM Comput. Surv. (CSUR)"},{"key":"464_CR14","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1016\/j.patrec.2014.11.013","volume":"55","author":"MM Hasan","year":"2015","unstructured":"Hasan, M.M., Islam, A.S., Rahman, M.S., et al.: Order preserving pattern matching revisited. Pattern Recogn. Lett. 55, 15\u201321 (2015)","journal-title":"Pattern Recogn. Lett."},{"issue":"6","key":"464_CR15","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. Exp. 10(6), 501\u2013506 (1980). https:\/\/doi.org\/10.1002\/spe.4380100608","journal-title":"Softw: Pract. Exp."},{"key":"464_CR16","volume-title":"An Introduction to Parallel Algorithms","author":"J J\u00e1J\u00e1","year":"1992","unstructured":"J\u00e1J\u00e1, J.: An Introduction to Parallel Algorithms, vol. 17. Addison-Wesley, Reading (1992)"},{"key":"464_CR17","doi-asserted-by":"crossref","unstructured":"Jargalsaikhan, D., Diptarama, Ueki, Y. et\u00a0al: Duel and sweep algorithm for order-preserving pattern matching. In: SOFSEM 2018: theory and practice of computer science 44th international conference on current trends in theory and practice of computer science, Krems, Austria, January 29-February 2, Proceedings pp 624-635, (2018)","DOI":"10.1007\/978-3-319-73117-9_44"},{"key":"464_CR18","doi-asserted-by":"crossref","unstructured":"Jargalsaikhan, D., Hendrian, D., Yoshinaka, R. et\u00a0al: Parallel duel-and-sweep algorithm for the order-preserving pattern matching. In: International conference on current trends in theory and practice of informatics, pp 211\u2013222 (2020)","DOI":"10.1007\/978-3-030-38919-2_18"},{"key":"464_CR19","doi-asserted-by":"publisher","unstructured":"Jargalsaikhan, D., Hendrian, D., Yoshinaka, R. et\u00a0al: Parallel algorithm for pattern matching problems under substring consistent equivalence relations. In: 33rd Annual symposium on combinatorial pattern matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic, LIPIcs, vol 223. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp 28:1\u201328:21, (2022a) https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2022.28","DOI":"10.4230\/LIPIcs.CPM.2022.28"},{"key":"464_CR20","unstructured":"Jargalsaikhan, D., Hendrian, D., Yoshinaka, R. et\u00a0al: Parallel algorithm for pattern matching problems under substring consistent equivalence relations. CoRR abs\/2202.13284. (2022b) https:\/\/arxiv.org\/abs\/2202.13284, 2202.13284"},{"key":"464_CR21","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., et al.: Order-preserving matching. Theoret. Comput. Sci. 525, 68\u201379 (2014)","journal-title":"Theoret. Comput. Sci."},{"issue":"2","key":"464_CR22","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J.H., Jr., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977). https:\/\/doi.org\/10.1137\/0206024","journal-title":"SIAM J. Comput."},{"issue":"12","key":"464_CR23","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., Kulczy\u0144ski, T., Radoszewski, J., et al.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett. 113(12), 430\u2013433 (2013)","journal-title":"Inf. Process. Lett."},{"key":"464_CR24","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1016\/j.tcs.2016.02.017","volume":"656","author":"Y Matsuoka","year":"2016","unstructured":"Matsuoka, Y., Aoki, T., Inenaga, S., et al.: Generalized pattern matching and periodicity under substring consistent equivalence relations. Theoret. Comput. Sci. 656, 225\u2013233 (2016)","journal-title":"Theoret. Comput. Sci."},{"key":"464_CR25","unstructured":"Ueki, Y., Narisawa, K., Shinohara, A.: A fast order-preserving matching with $$q$$-neighborhood filtration using SIMD instructions. In: SOFSEM (Student Research Forum Papers\/Posters), pp 108\u2013115 (2016)"},{"key":"464_CR26","first-page":"497","volume-title":"Optimal Parallel Pattern Matching in Strings. International Colloquium on Automata, Languages, and Programming","author":"U Vishkin","year":"1985","unstructured":"Vishkin, U.: Optimal Parallel Pattern Matching in Strings. International Colloquium on Automata, Languages, and Programming, pp. 497\u2013508. Springer, Berlin (1985)"},{"issue":"1","key":"464_CR27","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1137\/0220002","volume":"20","author":"U Vishkin","year":"1991","unstructured":"Vishkin, U.: Deterministic sampling: a new technique for fast pattern matching. SIAM J. Comput. 20(1), 22\u201340 (1991)","journal-title":"SIAM J. Comput."}],"container-title":["Acta Informatica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00464-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00236-024-00464-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00236-024-00464-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,4]],"date-time":"2024-11-04T11:03:45Z","timestamp":1730718225000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00236-024-00464-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,31]]},"references-count":27,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["464"],"URL":"https:\/\/doi.org\/10.1007\/s00236-024-00464-w","relation":{},"ISSN":["0001-5903","1432-0525"],"issn-type":[{"value":"0001-5903","type":"print"},{"value":"1432-0525","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,31]]},"assertion":[{"value":"1 April 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 August 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 August 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interests"}}]}}