{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:12:22Z","timestamp":1767139942669,"version":"build-2238731810"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T00:00:00Z","timestamp":1441670400000},"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":[[2017,1]]},"DOI":"10.1007\/s00453-015-0056-0","type":"journal-article","created":{"date-parts":[[2015,9,8]],"date-time":"2015-09-08T10:41:11Z","timestamp":1441708871000},"page":"134-150","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["A Grouping Approach for Succinct Dynamic Dictionary Matching"],"prefix":"10.1007","volume":"77","author":[{"given":"Guy","family":"Feigenblat","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ely","family":"Porat","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ariel","family":"Shiftan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,9,8]]},"reference":[{"issue":"2","key":"56_CR1","doi-asserted-by":"crossref","first-page":"208","DOI":"10.1016\/S0022-0000(05)80047-9","volume":"49","author":"A Amir","year":"1994","unstructured":"Amir, A., Farach, M., Galil, Z., Giancarlo, R., Park, K.: Dynamic dictionary matching. J. Comput. Syst. Sci. 49(2), 208\u2013222 (1994)","journal-title":"J. Comput. Syst. Sci."},{"key":"56_CR2","doi-asserted-by":"crossref","unstructured":"Sahinalp, S.C., Vishkin, U.: Efficient approximate and dynamic matching of patterns using a labeling paradigm. In: FOCS, IEEE Computer Society, pp. 320\u2013328 (1996)","DOI":"10.1109\/SFCS.1996.548491"},{"issue":"6","key":"56_CR3","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1145\/360825.360855","volume":"18","author":"AV Aho","year":"1975","unstructured":"Aho, A.V., Corasick, M.J.: Efficient string matching: an aid to bibliographic search. Commun. ACM 18(6), 333\u2013340 (1975)","journal-title":"Commun. ACM"},{"issue":"2","key":"56_CR4","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1006\/inco.1995.1090","volume":"119","author":"A Amir","year":"1995","unstructured":"Amir, A., Farach, M., Idury, R.M., Lapoutre, J.A., Schaffer, A.A.: Improved dynamic dictionary matching. Inf. Comput. 119(2), 258\u2013282 (1995)","journal-title":"Inf. Comput."},{"issue":"2","key":"56_CR5","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1137\/S0097539702402354","volume":"35","author":"R Grossi","year":"2005","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching. SIAM J. Comput. 35(2), 378\u2013407 (2005)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"56_CR6","doi-asserted-by":"crossref","first-page":"552","DOI":"10.1145\/1082036.1082039","volume":"52","author":"P Ferragina","year":"2005","unstructured":"Ferragina, P., Manzini, G.: Indexing compressed text. J. ACM 52(4), 552\u2013581 (2005)","journal-title":"J. ACM"},{"key":"56_CR7","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Ku, T.H., Lam, T.W., Shah, R., Tam, S.L., Thankachan, S.V., Vitter, J.S.: Compressing dictionary matching index via sparsification technique. Algorithmica 72(2), 515\u2013538 (2014)","DOI":"10.1007\/s00453-013-9863-3"},{"key":"56_CR8","unstructured":"Chan, H.L., Hon, W.K., Lam, T.W., Sadakane, K.: Dynamic dictionary matching and compressed suffix trees. In: Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201905, Philadelphia, PA, USA, pp. 13\u201322. Society for Industrial and Applied Mathematics (2005)"},{"issue":"2","key":"56_CR9","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris, J., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"56_CR10","doi-asserted-by":"crossref","first-page":"262","DOI":"10.1145\/321941.321946","volume":"23","author":"EM McCreight","year":"1976","unstructured":"McCreight, E.M.: A space-economical suffix tree construction algorithm. J. ACM 23(2), 262\u2013272 (1976)","journal-title":"J. ACM"},{"key":"56_CR11","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, FOCS \u201998, Washington, DC, USA, p. 534. IEEE Computer Society (1998)","DOI":"10.1109\/SFCS.1998.743504"},{"key":"56_CR12","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Lam, T.W., Shah, R., Tam, S.L., Vitter, J.S.: Compressed index for dictionary matching. In: Proceedings of the Data Compression Conference, DCC \u201908, Washington, DC, USA, pp. 23\u201332. IEEE Computer Society (2008)","DOI":"10.1109\/DCC.2008.62"},{"key":"56_CR13","doi-asserted-by":"crossref","unstructured":"Belazzougui, D.: Succinct dictionary matching with no slowdown. In: Proceedings of the 21st Annual Conference on Combinatorial Pattern Matching, CPM\u201910, pp. 88\u2013100. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-13509-5_9"},{"key":"56_CR14","doi-asserted-by":"crossref","unstructured":"Hon, W.K., Ku, T.H., Shah, R., Thankachan, S.V., Vitter, J.S.: Faster compressed dictionary matching. In: Proceedings of the 17th International Conference on String Processing and Information Retrieval, SPIRE\u201910, pp. 191\u2013200. Springer, Berlin (2010)","DOI":"10.1007\/978-3-642-16321-0_19"},{"key":"56_CR15","doi-asserted-by":"crossref","unstructured":"Rytter, W.: On maximal suffices and constant-space linear-time versions of kmp algorithm. In: Rajsbaum, S. (eds.) LATIN. Volume 2286 of Lecture Notes in Computer Science, pp. 196\u2013208. Springer (2002)","DOI":"10.1007\/3-540-45995-2_21"},{"key":"56_CR16","doi-asserted-by":"crossref","unstructured":"Sadakane, K., Navarro, G.: Fully-functional succinct trees. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA \u201910, Philadelphia, PA, USA, pp. 134\u2013149. Society for Industrial and Applied Mathematics (2010)","DOI":"10.1137\/1.9781611973075.13"},{"issue":"2","key":"56_CR17","doi-asserted-by":"crossref","first-page":"246","DOI":"10.1145\/321812.321820","volume":"21","author":"P Elias","year":"1974","unstructured":"Elias, P.: Efficient storage and retrieval by content and address of static files. J. ACM 21(2), 246\u2013260 (1974)","journal-title":"J. ACM"},{"key":"56_CR18","unstructured":"Fano, R.: On the Number of Bits Required to Implement an Associative Memory. Computation Structures Group Memo. MIT Project MAC Computer Structures Group (1971)"},{"key":"56_CR19","unstructured":"Grossi, R., Orlandi, A., Raman, R., Rao, S.S.: More haste, less waste: lowering the redundancy in fully indexable dictionaries. CoRR arXiv:0902.2648 (2009)"},{"key":"56_CR20","unstructured":"kai Hon, W., Sadakane, K., kin Sung, W.: Breaking a time-and-space barrier in constructing full-text indices. In: Proceedings of 44th Annual Symposium on Foundations of Computer Science, pp. 251\u2013260. IEEE (2003)"},{"key":"56_CR21","doi-asserted-by":"crossref","unstructured":"Munro, J.I.: Tables. In: FSTTCS. pp. 37\u201342 (1996)","DOI":"10.1007\/3-540-62034-6_35"},{"key":"56_CR22","doi-asserted-by":"crossref","unstructured":"Gabow, H.N., Tarjan, R.E.: A linear-time algorithm for a special case of disjoint set union. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC \u201983, New York, NY, USA, pp. 246\u2013251. ACM (1983)","DOI":"10.1145\/800061.808753"}],"updated-by":[{"DOI":"10.1007\/s00453-016-0183-2","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2016,7,12]],"date-time":"2016-07-12T00:00:00Z","timestamp":1468281600000}}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0056-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-015-0056-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0056-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-015-0056-0.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-0056-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,9,8]]},"references-count":22,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2017,1]]}},"alternative-id":["56"],"URL":"https:\/\/doi.org\/10.1007\/s00453-015-0056-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,9,8]]}}}