{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,14]],"date-time":"2026-03-14T21:39:45Z","timestamp":1773524385853,"version":"3.50.1"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T00:00:00Z","timestamp":1458518400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["0179\/DIA\/2013\/42"],"award-info":[{"award-number":["0179\/DIA\/2013\/42"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004569","name":"Ministerstwo Nauki i Szkolnictwa Wy\u017cszego","doi-asserted-by":"publisher","award":["0392\/IP3\/2015\/73"],"award-info":[{"award-number":["0392\/IP3\/2015\/73"]}],"id":[{"id":"10.13039\/501100004569","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["2014\/13\/B\/ST6\/00770"],"award-info":[{"award-number":["2014\/13\/B\/ST6\/00770"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2017,4]]},"DOI":"10.1007\/s00453-016-0140-0","type":"journal-article","created":{"date-parts":[[2016,3,21]],"date-time":"2016-03-21T10:52:49Z","timestamp":1458557569000},"page":"1194-1215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Efficient Indexes for Jumbled Pattern Matching with Constant-Sized Alphabet"],"prefix":"10.1007","volume":"77","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,3,21]]},"reference":[{"key":"140_CR1","doi-asserted-by":"publisher","unstructured":"Amir, A., Butman, A., Porat, E.: On the relationship between histogram indexing and block-mass indexing. Philos. Trans. A. Math. Phys. Eng. Sci. 372(2016), 20130132 (2014). doi: 10.1098\/rsta.2013.0132","DOI":"10.1098\/rsta.2013.0132"},{"key":"140_CR2","doi-asserted-by":"crossref","unstructured":"Amir, A., Chan, T.M., Lewenstein, M., Lewenstein, N.: On hardness of jumbled indexing. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) Automata, Languages, and Programming (ICALP 2014), Part I. LNCS, vol. 8572, pp. 114\u2013125. Springer, Berlin (2014)","DOI":"10.1007\/978-3-662-43948-7_10"},{"key":"140_CR3","doi-asserted-by":"crossref","unstructured":"Babenko, M., Gawrychowski, P., Kociumaka, T., Starikovskaya, T.: Wavelet trees meet suffix trees. In: Indyk, P. (ed.) 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pp. 572\u2013591. SIAM (2015)","DOI":"10.1137\/1.9781611973730.39"},{"key":"140_CR4","doi-asserted-by":"crossref","unstructured":"Bj\u00f6rklund, A., Kaski, P., Kowalik, \u0141.: Constrained multilinear detection and generalized graph motifs. Algorithmica 74(2), 947\u2013967 (2016)","DOI":"10.1007\/s00453-015-9981-1"},{"key":"140_CR5","doi-asserted-by":"crossref","unstructured":"Bremner, D., Chan, T.M., Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., P\u0103tra\u015fcu, M., Taslakian, P.: Necklaces, convolutions, and X + Y. Algorithmica 69(2), 294\u2013314 (2014)","DOI":"10.1007\/s00453-012-9734-3"},{"key":"140_CR6","doi-asserted-by":"crossref","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: On table arrangements, scrabble freaks, and jumbled pattern matching. In: Boldi, P., Gargano, L. (eds.) Fun with Algorithms (FUN 2010). LNCS, vol. 6099, pp. 89\u2013101. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13122-6_11"},{"issue":"2","key":"140_CR7","doi-asserted-by":"crossref","first-page":"357","DOI":"10.1142\/S0129054112400175","volume":"23","author":"P Burcsi","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Algorithms for jumbled pattern matching in strings. Int. J. Found. Comput. Sci. 23(2), 357\u2013374 (2012)","journal-title":"Int. J. Found. Comput. Sci."},{"issue":"1","key":"140_CR8","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/s00224-011-9344-5","volume":"50","author":"P Burcsi","year":"2012","unstructured":"Burcsi, P., Cicalese, F., Fici, G., Lipt\u00e1k, Z.: On approximate jumbled pattern matching in strings. Theory Comput. Syst. 50(1), 35\u201351 (2012)","journal-title":"Theory Comput. Syst."},{"issue":"6","key":"140_CR9","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/j.ipl.2004.09.002","volume":"92","author":"A Butman","year":"2004","unstructured":"Butman, A., Eres, R., Landau, G.M.: Scaled and permuted string matching. Inf. Process. Lett. 92(6), 293\u2013297 (2004)","journal-title":"Inf. Process. Lett."},{"key":"140_CR10","doi-asserted-by":"crossref","unstructured":"Chan, T.M., Lewenstein, M.: Clustered integer 3SUM via additive combinatorics. In: Servedio, R.A., Rubinfeld, R. (eds.) 47th Annual ACM Symposium on Theory of Computing (STOC 2015), pp. 31\u201340. ACM (2015)","DOI":"10.1145\/2746539.2746568"},{"key":"140_CR11","unstructured":"Cicalese, F., Fici, G., Lipt\u00e1k, Z.: Searching for jumbled patterns in strings. In: Holub, J., \u017d $$\\check{\\text{ d }}$$ d \u02c7 \u00e1rek, J. (eds.) Prague Stringology Conference 2009. Department of Computer Science and Engineering, Faculty of Electrical Engineering, Czech Technical University in Prague, Prague Stringology Club (2009)"},{"key":"140_CR12","doi-asserted-by":"crossref","unstructured":"Cicalese, F., Gagie, T., Giaquinta, E., Laber, E.S., Lipt\u00e1k, Z., Rizzi, R., Tomescu, A.I.: Indexes for jumbled pattern matching in strings, trees and graphs. In: Kurland, O., Lewenstein, M., Porat, E. (eds.) String Processing and Information Retrieval (SPIRE 2013). LNCS, vol. 8214, pp. 56\u201363. Springer, Berlin (2013)","DOI":"10.1007\/978-3-319-02432-5_10"},{"issue":"4","key":"140_CR13","doi-asserted-by":"crossref","first-page":"799","DOI":"10.1016\/j.jcss.2010.07.003","volume":"77","author":"MR Fellows","year":"2011","unstructured":"Fellows, M.R., Fertin, G., Hermelin, D., Vialette, S.: Upper and lower bounds for finding connected motifs in vertex-colored graphs. J. Comput. Syst. Sci. 77(4), 799\u2013811 (2011)","journal-title":"J. Comput. Syst. Sci."},{"issue":"3","key":"140_CR14","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1145\/828.1884","volume":"31","author":"ML Fredman","year":"1984","unstructured":"Fredman, M.L., Koml\u00f3s, J., Szemer\u00e9di, E.: Storing a sparse table with $$O(1)$$ O ( 1 ) worst case access time. J. ACM 31(3), 538\u2013544 (1984)","journal-title":"J. ACM"},{"issue":"3","key":"140_CR15","doi-asserted-by":"crossref","first-page":"571","DOI":"10.1007\/s00453-014-9957-6","volume":"73","author":"T Gagie","year":"2015","unstructured":"Gagie, T., Hermelin, D., Landau, G.M., Weimann, O.: Binary jumbled pattern matching on trees and tree-like structures. Algorithmica 73(3), 571\u2013588 (2015)","journal-title":"Algorithmica"},{"key":"140_CR16","doi-asserted-by":"crossref","unstructured":"Hagerup, T.: Sorting and searching on the word RAM. In: Morvan, M., Meinel, C., Krob, D. (eds.) Symposium on Theoretical Aspects of Computer Science (STACS 1998). LNCS, vol. 1373, pp. 366\u2013398. Springer, Berlin (1998)","DOI":"10.1007\/BFb0028575"},{"key":"140_CR17","unstructured":"Hermelin, D., Landau, G.M., Rabinovich, Y., Weimann, O.: Binary Jumbled Pattern Matching Via All-Pairs Shortest Paths. arXiv:1401.2065 (2014)"},{"key":"140_CR18","doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W.: Efficient indexes for jumbled pattern matching with constant-sized alphabet. In: Bodlaender, H.L., Italiano, G.F. (eds.) Algorithms (ESA 2013). LNCS, vol. 8125, pp. 625\u2013636. Springer, Berlin (2013)","DOI":"10.1007\/978-3-642-40450-4_53"},{"issue":"4","key":"140_CR19","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1109\/TCBB.2006.55","volume":"3","author":"V Lacroix","year":"2006","unstructured":"Lacroix, V., Fernandes, C.G., Sagot, M.: Motif search in graphs: application to metabolic networks. IEEE\/ACM Trans. Comput. Biol. Bioinform. 3(4), 360\u2013368 (2006)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinform."},{"issue":"18\u201319","key":"140_CR20","doi-asserted-by":"crossref","first-page":"795","DOI":"10.1016\/j.ipl.2010.06.012","volume":"110","author":"TM Moosa","year":"2010","unstructured":"Moosa, T.M., Rahman, M.S.: Indexing permutations for binary strings. Inf. Process. Lett. 110(18\u201319), 795\u2013798 (2010)","journal-title":"Inf. Process. Lett."},{"key":"140_CR21","doi-asserted-by":"crossref","first-page":"5","DOI":"10.1016\/j.jda.2011.08.003","volume":"10","author":"TM Moosa","year":"2012","unstructured":"Moosa, T.M., Rahman, M.S.: Sub-quadratic time and linear space data structures for permutation matching in binary strings. J. Discret. Algorithms 10, 5\u20139 (2012)","journal-title":"J. Discret. Algorithms"},{"key":"140_CR22","doi-asserted-by":"publisher","unstructured":"Munro, J.I., Nekrich, Y., Vitter, J.S.: Fast construction of wavelet trees. In: de Moura, E.S., Crochemore, M. (eds.) String Processing and Information Retrieval (SPIRE 2014). LNCS, vol. 8799, pp. 101\u2013110. Springer, Berlin (2014) (accepted to Theoretical Computer Science. doi: 10.1016\/j.tcs.2015.11.011 )","DOI":"10.1016\/j.tcs.2015.11.011"},{"key":"140_CR23","doi-asserted-by":"crossref","unstructured":"Williams, R.: Faster all-pairs shortest paths via circuit complexity. In: Shmoys, D.B. (ed.) 46th Annual ACM Symposium on Theory of Computing (STOC 2014), pp. 664\u2013673. ACM (2014)","DOI":"10.1145\/2591796.2591811"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0140-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0140-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0140-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0140-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,26]],"date-time":"2019-03-26T15:15:38Z","timestamp":1553613338000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0140-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,3,21]]},"references-count":23,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,4]]}},"alternative-id":["140"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0140-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,3,21]]}}}