{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,13]],"date-time":"2026-01-13T14:38:39Z","timestamp":1768315119765,"version":"3.49.0"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T00:00:00Z","timestamp":1564444800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T00:00:00Z","timestamp":1564444800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000083","name":"Directorate for Computer and Information Science and Engineering","doi-asserted-by":"publisher","award":["CCF 1218904"],"award-info":[{"award-number":["CCF 1218904"]}],"id":[{"id":"10.13039\/100000083","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s00453-019-00605-5","type":"journal-article","created":{"date-parts":[[2019,7,30]],"date-time":"2019-07-30T12:03:04Z","timestamp":1564488184000},"page":"107-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["Succinct Non-overlapping Indexing"],"prefix":"10.1007","volume":"82","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3331-0913","authenticated-orcid":false,"given":"Arnab","family":"Ganguly","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rahul","family":"Shah","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sharma V.","family":"Thankachan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,7,30]]},"reference":[{"issue":"1","key":"605_CR1","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/S1570-8667(03)00065-0","volume":"2","author":"MI Abouelhoda","year":"2004","unstructured":"Abouelhoda, M.I., Kurtz, S., Ohlebusch, E.: Replacing suffix trees with enhanced suffix arrays. J. Discrete Algorithms 2(1), 53\u201386 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"605_CR2","unstructured":"Alstrup, S., Brodal, G.S., Rauhe, T.: Optimal static range reporting in one dimension. In: Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6\u20138, 2001, Heraklion, Crete, Greece, pp. 476\u2013482 (2001)"},{"key":"605_CR3","unstructured":"Baker, B.S.: A theory of parameterized pattern matching: algorithms and applications. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, May 16\u201318, 1993, San Diego, CA, USA, pp. 71\u201380 (1993)"},{"issue":"10","key":"605_CR4","doi-asserted-by":"publisher","first-page":"762","DOI":"10.1145\/359842.359859","volume":"20","author":"RS Boyer","year":"1977","unstructured":"Boyer, R.S., Moore, J.S.: A fast string searching algorithm. Commun. ACM 20(10), 762\u2013772 (1977)","journal-title":"Commun. ACM"},{"key":"605_CR5","unstructured":"Brodal, G.S., Fagerberg, R., Greve, M., L\u00f3pez-Ortiz, A.: Online sorted range reporting. In: Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16\u201318, 2009. Proceedings, pp. 173\u2013182 (2009)"},{"key":"605_CR6","unstructured":"Cohen, H., Porat, E.: Range non-overlapping indexing. In: Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16\u201318, 2009. Proceedings, pp. 1044\u20131053 (2009)"},{"key":"605_CR7","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13\u201316, 2004, pp. 91\u2013100 (2004)"},{"key":"605_CR8","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Rahman, M.S., Walen, T.: Improved algorithms for the range next value problem and applications. In: STACS 2008, 25th Annual Symposium on Theoretical Aspects of Computer Science, Bordeaux, France, February 21\u201323, 2008, Proceedings, pp. 205\u2013216 (2008)"},{"key":"605_CR9","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In: 38th Annual Symposium on Foundations of Computer Science, FOCS \u201997, Miami Beach, Florida, USA, October 19\u201322, 1997, pp. 137\u2013143 (1997)"},{"issue":"4","key":"605_CR10","doi-asserted-by":"publisher","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":"605_CR11","unstructured":"Ganguly, A., Shah, R., Thankachan, S.V.: Succinct non-overlapping indexing. In: Combinatorial Pattern Matching\u201426th Annual Symposium, CPM 2015, Ischia Island, Italy, June 29\u2013July 1, 2015, Proceedings, pp. 185\u2013195 (2015)"},{"key":"605_CR12","doi-asserted-by":"crossref","unstructured":"Ganguly, A., Shah, R., Thankachan, S.V: pBWT: achieving succinct data structures for parameterized pattern matching and related problems. In: Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 397\u2013407. Society for Industrial and Applied Mathematics (2017)","DOI":"10.1137\/1.9781611974782.25"},{"key":"605_CR13","unstructured":"Ganguly, A., Shah, R., Thankachan, S.V.: Structural pattern matching-succinctly. In: 28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9\u201312, 2017, Phuket, Thailand, pp. 35:1\u201335:13 (2017)"},{"key":"605_CR14","unstructured":"Grossi, R., Vitter, J.S.: Compressed suffix arrays and suffix trees with applications to text indexing and string matching (extended abstract). In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, May 21\u201323, 2000, Portland, OR, USA, pp. 397\u2013406 (2000)"},{"key":"605_CR15","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, Cambridge (1997)"},{"key":"605_CR16","doi-asserted-by":"publisher","first-page":"109","DOI":"10.1016\/j.jda.2012.09.002","volume":"17","author":"W-K Hon","year":"2012","unstructured":"Hon, W.-K., Shah, R., Thankachan, S.V., Vitter, J.S.: On position restricted substring searching in succinct space. J. Discrete Algorithms 17, 109\u2013114 (2012)","journal-title":"J. Discrete Algorithms"},{"key":"605_CR17","unstructured":"Hooshmand, S., Abedin, P., K\u00fclekci, M.O., Thankachan, S.V.: Non-overlapping indexing: cache obliviously. In: Annual Symposium on Combinatorial Pattern Matching, CPM 2018, July 2\u20134, 2018 - Qingdao, China, pp. 8:1\u20138:9 (2018)"},{"issue":"2","key":"605_CR18","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1147\/rd.312.0249","volume":"31","author":"RM Karp","year":"1987","unstructured":"Karp, R.M., Rabin, M.O.: Efficient randomized pattern-matching algorithms. IBM J. Res. Dev. 31(2), 249\u2013260 (1987)","journal-title":"IBM J. Res. Dev."},{"key":"605_CR19","unstructured":"Keller, O., Kopelowitz, T., Lewenstein, M.: Range non-overlapping indexing and successive list indexing. In: Algorithms and Data Structures, 10th International Workshop, WADS 2007, Halifax, Canada, August 15\u201317, 2007, Proceedings, pp. 625\u2013636 (2007)"},{"issue":"2","key":"605_CR20","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1137\/0206024","volume":"6","author":"DE Knuth","year":"1977","unstructured":"Knuth, D.E., Morris Jr., J.H., Pratt, V.R.: Fast pattern matching in strings. SIAM J. Comput. 6(2), 323\u2013350 (1977)","journal-title":"SIAM J. Comput."},{"key":"605_CR21","unstructured":"M\u00e4kinen, V., Navarro, G.: Position-restricted substring searching. In: LATIN 2006: Theoretical Informatics, 7th Latin American Symposium, Valdivia, Chile, March 20\u201324, 2006, Proceedings, pp. 703\u2013714 (2006)"},{"issue":"5","key":"605_CR22","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: a new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"key":"605_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1216370.1216372","volume":"39","author":"G Navarro","year":"2007","unstructured":"Navarro, G., M\u00e4kinen, V.: Compressed full-text indexes. ACM Comput. Surv. 39, 1 (2007)","journal-title":"ACM Comput. Surv."},{"key":"605_CR24","unstructured":"Nekrich, Y., Navarro, G.: Sorted range reporting. In: Algorithm Theory\u2014SWAT 2012: 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4\u20136, 2012. Proceedings, pp. 271\u2013282 (2012)"},{"issue":"3","key":"605_CR25","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1007\/BF01206331","volume":"14","author":"E Ukkonen","year":"1995","unstructured":"Ukkonen, E.: On-line construction of suffix trees. Algorithmica 14(3), 249\u2013260 (1995)","journal-title":"Algorithmica"},{"key":"605_CR26","doi-asserted-by":"crossref","unstructured":"Weiner, P.: Linear pattern matching algorithms. In: 14th Annual Symposium on Switching and Automata Theory, Iowa City, Iowa, USA, October 15\u201317, 1973, pp. 1\u201311 (1973)","DOI":"10.1109\/SWAT.1973.13"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00605-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-019-00605-5\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-019-00605-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,28]],"date-time":"2020-07-28T23:15:03Z","timestamp":1595978103000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-019-00605-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,7,30]]},"references-count":26,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["605"],"URL":"https:\/\/doi.org\/10.1007\/s00453-019-00605-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,30]]},"assertion":[{"value":"4 November 2015","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 July 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 July 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}