{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,25]],"date-time":"2026-02-25T22:29:12Z","timestamp":1772058552958,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2015,9,30]],"date-time":"2015-09-30T00:00:00Z","timestamp":1443571200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d (DK)","doi-asserted-by":"publisher","award":["1323-00178"],"award-info":[{"award-number":["1323-00178"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d (DK)","doi-asserted-by":"publisher","award":["1323-00178"],"award-info":[{"award-number":["1323-00178"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d (DK)","doi-asserted-by":"publisher","award":["4005-00267"],"award-info":[{"award-number":["4005-00267"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d (DK)","doi-asserted-by":"publisher","award":["4005-00267"],"award-info":[{"award-number":["4005-00267"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004836","name":"Det Frie Forskningsr\u00e5d (DK)","doi-asserted-by":"publisher","award":["4005-00267"],"award-info":[{"award-number":["4005-00267"]}],"id":[{"id":"10.13039\/501100004836","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,2]]},"DOI":"10.1007\/s00453-015-0068-9","type":"journal-article","created":{"date-parts":[[2015,9,30]],"date-time":"2015-09-30T10:01:47Z","timestamp":1443607307000},"page":"336-348","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Compressed Subsequence Matching and Packed Tree Coloring"],"prefix":"10.1007","volume":"77","author":[{"given":"Philip","family":"Bille","sequence":"first","affiliation":[]},{"given":"Patrick Hagge","family":"Cording","sequence":"additional","affiliation":[]},{"given":"Inge Li","family":"G\u00f8rtz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,9,30]]},"reference":[{"issue":"6","key":"68_CR1","doi-asserted-by":"crossref","first-page":"1295","DOI":"10.1137\/S0097539703437211","volume":"35","author":"S Abiteboul","year":"2006","unstructured":"Abiteboul, S., Alstrup, S., Kaplan, H., Milo, T., Rauhe, T.: Compact labeling scheme for ancestor queries. SIAM J. Comput. 35(6), 1295\u20131309 (2006)","journal-title":"SIAM J. Comput."},{"key":"68_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/3-540-45022-X_8","volume-title":"Automata, Languages and Programming","author":"S Alstrup","year":"2000","unstructured":"Alstrup, S., Holm, J.: Improved algorithms for finding level ancestors in dynamic trees. In: Montanari, U., Rolim, J.P., Welzl, E. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 1853, pp. 73\u201384. Springer, Berlin, Heidelberg (2000)"},{"key":"68_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"270","DOI":"10.1007\/3-540-63165-8_184","volume-title":"Automata, Languages and Programming","author":"S Alstrup","year":"1997","unstructured":"Alstrup, S., Holm, J., de Lichtenberg, K., Thorup, M.: Minimizing diameters of dynamic trees. In: Degano, P., Gorrieri, R., Marchetti-Spaccamela, A. (eds.) Automata, Languages and Programming. Lecture Notes in Computer Science, vol. 1256, pp. 270\u2013280. Springer, Berlin, Heidelberg (1997)"},{"key":"68_CR4","doi-asserted-by":"crossref","unstructured":"Alstrup, S., Husfeldt, T., Rauhe, T.: Marked ancestor problems. In: Proceedings of the 39th Annual Symposium on Foundations of Computer Science, pp. 534\u2013543. IEEE Computer Society, Washington, DC (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"issue":"4","key":"68_CR5","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(97)00170-1","volume":"64","author":"S Alstrup","year":"1997","unstructured":"Alstrup, S., Secher, J.P., Spork, M.: Optimal on-line decremental connectivity in trees. Inf. Process. Lett. 64(4), 161\u2013164 (1997)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"68_CR6","doi-asserted-by":"crossref","first-page":"363","DOI":"10.1016\/0304-3975(91)90358-9","volume":"78","author":"RA Baeza-Yates","year":"1991","unstructured":"Baeza-Yates, R.A.: Searching subsequences. Theor. Comput. Sci. 78(2), 363\u2013376 (1991)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"68_CR7","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.tcs.2003.05.002","volume":"321","author":"MA Bender","year":"2004","unstructured":"Bender, M.A., Farach-Colton, M.: The level ancestor problem simplified. Theor. Comput. Sci. 321(1), 5\u201312 (2004)","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"68_CR8","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1016\/S0022-0000(05)80002-9","volume":"48","author":"O Berkman","year":"1994","unstructured":"Berkman, O., Vishkin, U.: Finding level-ancestors in trees. J. Comput. Syst. Sci. 48(2), 214\u2013230 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"68_CR9","doi-asserted-by":"crossref","unstructured":"Bille, P., Landau, G.M., Raman, R., Sadakane, K., Satti, S.R., Weimann, O.: Random access to grammar-compressed strings. In: Proceedings of the Twenty-second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 373\u2013389. SIAM, San Francisco (2011)","DOI":"10.1137\/1.9781611973082.30"},{"issue":"1","key":"68_CR10","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1016\/S0168-0072(01)00051-3","volume":"113","author":"L Boasson","year":"2001","unstructured":"Boasson, L., Cegielski, P., Guessarian, I., Matiyasevich, Y.: Window-accumulated subsequence matching problem is linear. Ann. Pure Appl. Log. 113(1), 59\u201380 (2001)","journal-title":"Ann. Pure Appl. Log."},{"key":"68_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/11753728_15","volume-title":"Computer Science-Theory and Applications","author":"P C\u00e9gielski","year":"2006","unstructured":"C\u00e9gielski, P., Guessarian, I., Lifshits, Y., Matiyasevich, Y.: Window subsequence problems for compressed texts. In: Grigoriev, D., Harrison, J., Hirsch, E.A. (eds.) Computer Science-Theory and Applications. Lecture Notes in Computer Science, vol. 3967, pp. 127\u2013136. Springer, Berlin, Heidelberg (2006)"},{"issue":"6","key":"68_CR12","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/j.ipl.2006.02.008","volume":"98","author":"P C\u00e9gielski","year":"2006","unstructured":"C\u00e9gielski, P., Guessarian, I., Matiyasevich, Y.: Multiple serial episodes matching. Inf. Proc. Lett. 98(6), 211\u2013218 (2006)","journal-title":"Inf. Proc. Lett."},{"issue":"7","key":"68_CR13","doi-asserted-by":"crossref","first-page":"2554","DOI":"10.1109\/TIT.2005.850116","volume":"51","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Lehman, E., Liu, D., Panigrahy, R., Prabhakaran, M., Sahai, A., Shelat, A.: The smallest grammar problem. IEEE Trans. Inf. Theory 51(7), 2554\u20132576 (2005)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"68_CR14","doi-asserted-by":"crossref","first-page":"255","DOI":"10.1016\/S1570-8667(03)00029-7","volume":"1","author":"M Crochemore","year":"2003","unstructured":"Crochemore, M., Melichar, B., Tron\u00ed\u010dek, Z.: Directed acyclic subsequence graph\u2014overview. J. Discret. Algorithms 1(3), 255\u2013280 (2003)","journal-title":"J. Discret. Algorithms"},{"key":"68_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1007\/3-540-63220-4_46","volume-title":"Combinatorial Pattern Matching","author":"G Das","year":"1997","unstructured":"Das, G., Fleischer, R., Gasieniec, L., Gunopulos, D., K\u00e4rkk\u00e4inen, J.: Episode matching. In: Apostolico, A., Hein, J. (eds.) Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 1264, pp. 12\u201327. Springer, Berlin, Heidelberg (1997)"},{"key":"68_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/BFb0028247","volume-title":"Algorithms and Data Structures","author":"PF Dietz","year":"1991","unstructured":"Dietz, P.F.: Finding level-ancestors in dynamic trees. In: Dehne, F., Sack, J.-R., Santoro, N. (eds.) Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 519, pp. 32\u201340. Springer, Berlin, Heidelberg (1991)"},{"key":"68_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1007\/3-540-61680-2_50","volume-title":"European Symposium on Algorithms","author":"P Ferragina","year":"1996","unstructured":"Ferragina, P., Muthukrishnan, S.: Efficient dynamic method-lookup for object oriented languages. In: Diaz, J., Serna, M. (eds.) European Symposium on Algorithms. Lecture Notes in Computer Science, vol. 1136, pp. 107\u2013120. Springer, Berlin, Heidelberg (1996)"},{"issue":"3","key":"68_CR18","doi-asserted-by":"crossref","first-page":"424","DOI":"10.1016\/0022-0000(93)90040-4","volume":"47","author":"ML Fredman","year":"1993","unstructured":"Fredman, M.L., Willard, D.E.: Surpassing the information theoretic bound with fusion trees. J. Comput. Syst. Sci. 47(3), 424\u2013436 (1993)","journal-title":"J. Comput. Syst. Sci."},{"key":"68_CR19","doi-asserted-by":"crossref","unstructured":"Larsson, N.J., Moffat, A.: Off-line dictionary-based compression. P. IEEE. 88(11), 1722\u20131732 (2000)","DOI":"10.1109\/5.892708"},{"issue":"3","key":"68_CR20","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1023\/A:1009748302351","volume":"1","author":"H Mannila","year":"1997","unstructured":"Mannila, H., Toivonen, H., Verkamo, A.I.: Discovery of frequent episodes in event sequences. Data Min. Knowl. Disc. 1(3), 259\u2013289 (1997)","journal-title":"Data Min. Knowl. Disc."},{"key":"68_CR21","unstructured":"Muthukrishnan, S., M\u00fcller, M.: Time and space efficient method-lookup for object-oriented programs. In: Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 42\u201351. Society for Industrial and Applied Mathematics, Atlanta (1996)"},{"issue":"1","key":"68_CR22","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/S0304-3975(02)00777-6","volume":"302","author":"W Rytter","year":"2003","unstructured":"Rytter, W.: Application of Lempel\u2013Ziv factorization to the approximation of grammar-based compression. Theor. Comput. Sci. 302(1), 211\u2013222 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"68_CR23","doi-asserted-by":"crossref","first-page":"362","DOI":"10.1016\/0022-0000(83)90006-5","volume":"26","author":"DD Sleator","year":"1983","unstructured":"Sleator, D.D., Endre Tarjan, R.: A data structure for dynamic trees. J. Comput. Syst. Sci. 26(3), 362\u2013391 (1983)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"68_CR24","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1006\/jagm.2002.1211","volume":"42","author":"M Thorup","year":"2002","unstructured":"Thorup, M.: Randomized sorting in $$O(n\\log \\log n)$$ O ( n log log n ) time and linear space using addition, shift, and bit-wise boolean operations. J. Algorithms 42(2), 205\u2013230 (2002)","journal-title":"J. Algorithms"},{"issue":"5","key":"68_CR25","doi-asserted-by":"crossref","first-page":"759","DOI":"10.1007\/s10958-009-9396-0","volume":"158","author":"A Tiskin","year":"2009","unstructured":"Tiskin, A.: Faster subsequence recognition in compressed strings. J. Math. Sci. 158(5), 759\u2013769 (2009)","journal-title":"J. Math. Sci."},{"key":"68_CR26","doi-asserted-by":"crossref","first-page":"401","DOI":"10.1007\/978-3-642-20712-9_32","volume-title":"Computer Science-Theory and Applications","author":"A Tiskin","year":"2011","unstructured":"Tiskin, A.: Towards approximate matching in compressed strings: local subsequence recognition. In: Kulikov, A., Vereshchagin, N. (eds.) Computer Science-Theory and Applications, vol. 6651, pp. 401\u2013414. Springer, Berlin, Heidelberg (2011)"},{"key":"68_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-48194-X_12","volume-title":"Combinatorial Pattern Matching","author":"Z Tron\u00ed\u010dek","year":"2001","unstructured":"Tron\u00ed\u010dek, Z.: Episode matching. In: Amir, A. (ed.) Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 2089, pp. 143\u2013146. Springer, Berlin, Heidelberg (2001)"},{"key":"68_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1007\/978-3-642-21458-5_27","volume-title":"Combinatorial Pattern Matching","author":"T Yamamoto","year":"2011","unstructured":"Yamamoto, T., Bannai, H., Inenaga, S., Takeda, M.: Faster subsequence and dont-care pattern matching on compressed texts. In: Giancarlo, R., Manzini, G. (eds.) Combinatorial Pattern Matching. Lecture Notes in Computer Science, vol. 6661, pp. 309\u2013322. Springer, Berlin, Heidelberg (2011)"},{"issue":"3","key":"68_CR29","doi-asserted-by":"crossref","first-page":"337","DOI":"10.1109\/TIT.1977.1055714","volume":"23","author":"J Ziv","year":"1977","unstructured":"Ziv, J., Lempel, A.: A universal algorithm for sequential data compression. IEEE Trans. Inf. Theory 23(3), 337\u2013343 (1977)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"68_CR30","doi-asserted-by":"crossref","first-page":"530","DOI":"10.1109\/TIT.1978.1055934","volume":"24","author":"J Ziv","year":"1978","unstructured":"Ziv, J., Lempel, A.: Compression of individual sequences via variable-rate coding. IEEE Trans. Inf. Theory 24(5), 530\u2013536 (1978)","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0068-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0068-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0068-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0068-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:22Z","timestamp":1559072842000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-015-0068-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,30]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,2]]}},"alternative-id":["68"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0068-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,30]]}}}