{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,18]],"date-time":"2026-07-18T16:26:05Z","timestamp":1784391965980,"version":"3.55.0"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,6,16]],"date-time":"2015-06-16T00:00:00Z","timestamp":1434412800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,5]]},"DOI":"10.1007\/s00453-015-0013-y","type":"journal-article","created":{"date-parts":[[2015,6,15]],"date-time":"2015-06-15T14:10:16Z","timestamp":1434377416000},"page":"84-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["A Fast Algorithm for Permutation Pattern Matching Based on Alternating Runs"],"prefix":"10.1007","volume":"75","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9916-9011","authenticated-orcid":false,"given":"Marie-Louise","family":"Bruner","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin","family":"Lackner","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2015,6,16]]},"reference":[{"issue":"2","key":"13_CR1","doi-asserted-by":"crossref","first-page":"629","DOI":"10.1137\/S0895480104444776","volume":"22","author":"S Ahal","year":"2008","unstructured":"Ahal, S., Rabinovich, Y.: On complexity of the subpattern problem. SIAM J. Discrete Math. 22(2), 629\u2013649 (2008)","journal-title":"SIAM J. Discrete Math."},{"key":"13_CR2","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1007\/3-540-45678-3_31","volume-title":"Algorithms and Computation, Lecture Notes in Computer Science","author":"M Albert","year":"2001","unstructured":"Albert, M., Aldred, R., Atkinson, M., Holton, D.: Algorithms for pattern involvement in permutations. In: Eades, P., Takaoka, T. (eds.) Algorithms and Computation, Lecture Notes in Computer Science, vol. 2223, pp. 355\u2013367. Springer, Berlin (2001)"},{"key":"13_CR3","first-page":"225","volume":"28","author":"MH Albert","year":"2003","unstructured":"Albert, M.H., Aldred, R.E.L., Atkinson, M.D., van Ditmarsch, H.P., Handley, B.D., Handley, C.C., Opatrny, J.: Longest subsequences in permutations. Australas. J. Comb. 28, 225\u2013238 (2003)","journal-title":"Australas. J. Comb."},{"issue":"1","key":"13_CR4","doi-asserted-by":"crossref","first-page":"121","DOI":"10.24033\/asens.235","volume":"3","author":"D Andr\u00e9","year":"1884","unstructured":"Andr\u00e9, D.: \u00c9tude sur les maxima, minima et s\u00e9quences des permutations. Annales scientifiques de l\u2019\u00c9cole normale sup\u00e9rieure 3(1), 121\u2013135 (1884)","journal-title":"Annales scientifiques de l\u2019\u00c9cole normale sup\u00e9rieure"},{"key":"13_CR5","doi-asserted-by":"crossref","DOI":"10.1201\/9780203494370","volume-title":"Combinatorics of Permutations. Discrete Mathematics and Its Applications","author":"M B\u00f3na","year":"2004","unstructured":"B\u00f3na, M.: Combinatorics of Permutations. Discrete Mathematics and Its Applications. Chapman & Hall\/CRC, Boca Raton (2004)"},{"issue":"5","key":"13_CR6","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1016\/S0020-0190(97)00209-3","volume":"65","author":"P Bose","year":"1998","unstructured":"Bose, P., Buss, J.F., Lubiw, A.: Pattern matching for permutations. Inf. Process. Lett. 65(5), 277\u2013283 (1998)","journal-title":"Inf. Process. Lett."},{"issue":"1\u20132","key":"13_CR7","first-page":"55","volume":"17","author":"M Bouvel","year":"2006","unstructured":"Bouvel, M., Rossin, D.: The longest common pattern problem for two permutations. Pure Math. Appl. 17(1\u20132), 55\u201369 (2006)","journal-title":"Pure Math. Appl."},{"key":"13_CR8","doi-asserted-by":"crossref","first-page":"316","DOI":"10.1007\/978-3-540-73437-6_32","volume-title":"Combinatorial Pattern Matching, Lecture Notes in Computer Science","author":"M Bouvel","year":"2007","unstructured":"Bouvel, M., Rossin, D., Vialette, S.: Longest common separable pattern among permutations. In: Ma, B., Zhang, K. (eds.) Combinatorial Pattern Matching, Lecture Notes in Computer Science, pp. 316\u2013327. Springer, Berlin (2007)"},{"key":"13_CR9","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1007\/978-3-642-31155-0_23","volume-title":"Algorithm Theory\u2014SWAT 2012, Lecture Notes in Computer Science","author":"ML Bruner","year":"2012","unstructured":"Bruner, M.L., Lackner, M.: A fast algorithm for permutation pattern matching based on alternating runs. In: Fomin, F.V., Kaski, P. (eds.) Algorithm Theory\u2014SWAT 2012, Lecture Notes in Computer Science, vol. 7357, pp. 261\u2013270. Springer, Berlin (2012)"},{"issue":"2","key":"13_CR10","first-page":"83","volume":"24","author":"ML Bruner","year":"2013","unstructured":"Bruner, M.L., Lackner, M.: The computational landscape of permutation patterns. Pure Math. Appl. 24(2), 83\u2013101 (2013)","journal-title":"Pure Math. Appl."},{"issue":"6","key":"13_CR11","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0020-0190(92)90114-B","volume":"43","author":"MS Chang","year":"1992","unstructured":"Chang, M.S., Wang, F.H.: Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs. Inf. Process. Lett. 43(6), 293\u2013295 (1992)","journal-title":"Inf. Process. Lett."},{"key":"13_CR12","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1007\/978-3-319-02432-5_13","volume-title":"String Processing and Information Retrieval, Lecture Notes in Computer Science","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.) String Processing and Information Retrieval, Lecture Notes in Computer Science, vol. 8214, pp. 84\u201395. Springer, Berlin (2013)"},{"key":"13_CR13","volume-title":"Combinatorial Chance","author":"FN David","year":"1962","unstructured":"David, F.N., Barton, D.E.: Combinatorial Chance. Griffin, London (1962)"},{"key":"13_CR14","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4471-5559-1","volume-title":"Fundamentals of Parameterized Complexity. Texts in Computer Science","author":"R Downey","year":"2013","unstructured":"Downey, R., Fellows, M.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, Berlin (2013)"},{"key":"13_CR15","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-0515-9","volume-title":"Parameterized Complexity","author":"RG Downey","year":"1999","unstructured":"Downey, R.G., Fellows, M.R.: Parameterized Complexity. Springer, Berlin (1999)"},{"key":"13_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801655","volume-title":"Analytic Combinatorics","author":"P Flajolet","year":"2009","unstructured":"Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)"},{"key":"13_CR17","volume-title":"Parameterized Complexity Theory","author":"J Flum","year":"2006","unstructured":"Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006)"},{"key":"13_CR18","volume-title":"Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series","author":"F Fomin","year":"2010","unstructured":"Fomin, F., Kratsch, D.: Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2010)"},{"key":"13_CR19","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1007\/978-3-319-07566-2_14","volume-title":"Combinatorial Pattern Matching, Lecture Notes in Computer Science","author":"P Gawrychowski","year":"2014","unstructured":"Gawrychowski, P., Uzna\u0144ski, P.: Order-preserving pattern matching with $$k$$ k mismatches. In: Kulikov, A.S., Kuznetsov, S.O., Pevzner, P. (eds.) Combinatorial Pattern Matching, Lecture Notes in Computer Science, vol. 8486, pp. 130\u2013139. Springer, Berlin (2014)"},{"key":"13_CR20","doi-asserted-by":"crossref","unstructured":"Guillemot, S., Marx, D.: Finding small patterns in permutations in linear time. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA\u201914, pp. 82\u2013101. SIAM (2014)","DOI":"10.1137\/1.9781611973402.7"},{"key":"13_CR21","doi-asserted-by":"crossref","first-page":"1064","DOI":"10.1007\/978-3-642-10631-6_107","volume-title":"Algorithms and Computation, Lecture Notes in Computer Science","author":"S Guillemot","year":"2009","unstructured":"Guillemot, S., Vialette, S.: Pattern matching for 321-avoiding permutations. In: Dong, Y., Du, D.Z., Ibarra, O. (eds.) Algorithms and Computation, Lecture Notes in Computer Science, vol. 5878, pp. 1064\u20131073. Springer, Berlin (2009)"},{"issue":"1","key":"13_CR22","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1145\/1233481.1233493","volume":"38","author":"J Guo","year":"2007","unstructured":"Guo, J., Niedermeier, R.: Invitation to data reduction and problem kernelization. SIGACT News 38(1), 31\u201345 (2007)","journal-title":"SIGACT News"},{"issue":"6","key":"13_CR23","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/S0020-0190(97)00029-X","volume":"61","author":"L Ibarra","year":"1997","unstructured":"Ibarra, L.: Finding pattern matchings for permutations. Inf. Process. Lett. 61(6), 293\u2013295 (1997)","journal-title":"Inf. Process. Lett."},{"key":"13_CR24","doi-asserted-by":"crossref","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.H., 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."},{"key":"13_CR25","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-17333-2","volume-title":"Patterns in Permutations and Words","author":"S Kitaev","year":"2011","unstructured":"Kitaev, S.: Patterns in Permutations and Words. Springer, Berlin (2011)"},{"key":"13_CR26","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-84800-048-3","volume-title":"Probability Theory: A Comprehensive Course","author":"A Klenke","year":"2008","unstructured":"Klenke, A.: Probability Theory: A Comprehensive Course. Springer, Berlin (2008)"},{"key":"13_CR27","volume-title":"The Art of Computer Programming: Fundamental Algorithms","author":"DE Knuth","year":"1968","unstructured":"Knuth, D.E.: The Art of Computer Programming: Fundamental Algorithms, vol. I. Addison-Wesley, Reading (1968)"},{"issue":"12","key":"13_CR28","doi-asserted-by":"crossref","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., Rytter, W., Wale, T.: A linear time algorithm for consecutive permutation pattern matching. Inf. Process. Lett. 113(12), 430\u2013433 (2013)","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"13_CR29","doi-asserted-by":"crossref","first-page":"58","DOI":"10.1214\/aoms\/1177731314","volume":"15","author":"H Levene","year":"1944","unstructured":"Levene, H., Wolfowitz, J.: The covariance matrix of runs up and down. Ann. Math. Stat. 15(1), 58\u201369 (1944)","journal-title":"Ann. Math. Stat."},{"issue":"1","key":"13_CR30","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1080\/00207160108805049","volume":"77","author":"E M\u00e4kinen","year":"2001","unstructured":"M\u00e4kinen, E.: On the longest upsequence problem for permutations. Int. J. Comput. Math. 77(1), 45\u201353 (2001)","journal-title":"Int. J. Comput. Math."},{"key":"13_CR31","doi-asserted-by":"crossref","DOI":"10.1093\/acprof:oso\/9780198566076.001.0001","volume-title":"Invitation to Fixed-Parameter Algorithms, Lecture Series in Mathematics and Its Applications","author":"R Niedermeier","year":"2006","unstructured":"Niedermeier, R.: Invitation to Fixed-Parameter Algorithms, Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)"},{"issue":"3","key":"13_CR32","doi-asserted-by":"crossref","first-page":"343","DOI":"10.1016\/j.dam.2004.10.004","volume":"146","author":"S Saxena","year":"2005","unstructured":"Saxena, S., Yugandhar, V.: Parallel algorithms for separable permutations. Discrete Appl. Math. 146(3), 343\u2013364 (2005)","journal-title":"Discrete Appl. Math."},{"key":"13_CR33","doi-asserted-by":"crossref","unstructured":"Schensted, C.: Longest increasing and decreasing subsequences. Canad. J. Math. 13,179\u2013191(1961)","DOI":"10.4153\/CJM-1961-015-3"},{"key":"13_CR34","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1016\/S0195-6698(85)80052-4","volume":"6","author":"R Simion","year":"1985","unstructured":"Simion, R., Schmidt, F.W.: Restricted permutations. Eur. J. Comb. 6, 383\u2013406 (1985)","journal-title":"Eur. J. Comb."},{"key":"13_CR35","volume-title":"Handbook of Theoretical Computer Science","author":"P Emde Boas Van","year":"1990","unstructured":"Van Emde Boas, P.: Machine models and simulations. In: Van Leeuwen, J. (ed.) Handbook of Theoretical Computer Science, vol. A. Elsevier, Amsterdam (1990)"},{"key":"13_CR36","volume-title":"Handbook of Enumerative Combinatorics","author":"V Vatter","year":"2015","unstructured":"Vatter, V.: Permutation patterns. In: B\u00f3na, M. (ed.) Handbook of Enumerative Combinatorics. CRC Press, Boca Raton (2015)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0013-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0013-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0013-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,28]],"date-time":"2025-05-28T17:00:15Z","timestamp":1748451615000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0013-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,16]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2016,5]]}},"alternative-id":["13"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0013-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,6,16]]}}}