{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:29Z","timestamp":1759638149595},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319460482"},{"type":"electronic","value":"9783319460499"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-46049-9_3","type":"book-chapter","created":{"date-parts":[[2016,9,20]],"date-time":"2016-09-20T11:02:06Z","timestamp":1474369326000},"page":"22-34","source":"Crossref","is-referenced-by-count":4,"title":["Near-Optimal Computation of Runs over General Alphabet via Non-Crossing LCE Queries"],"prefix":"10.1007","author":[{"given":"Maxime","family":"Crochemore","sequence":"first","affiliation":[]},{"given":"Costas S.","family":"Iliopoulos","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Kociumaka","sequence":"additional","affiliation":[]},{"given":"Ritu","family":"Kundu","sequence":"additional","affiliation":[]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]},{"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]},{"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,21]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: A new characterization of maximal repetitions by Lyndon trees. In: Indyk, P. (ed.) 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 562\u2013571. SIAM (2015)","key":"3_CR1","DOI":"10.1137\/1.9781611973730.38"},{"unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem (2015). arXiv:1406.0263v7","key":"3_CR2"},{"issue":"1","key":"3_CR3","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/0097-3165(90)90050-7","volume":"55","author":"H Barcelo","year":"1990","unstructured":"Barcelo, H.: On the action of the symmetric group on the free Lie algebra and the partition lattice. J. Comb. Theory, Ser. A 55(1), 93\u2013129 (1990)","journal-title":"J. Comb. Theory, Ser. A"},{"key":"3_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"342","DOI":"10.1007\/3-540-48447-7_34","volume-title":"Algorithms and Data Structures","author":"GS Brodal","year":"1999","unstructured":"Brodal, G.S., Fagerberg, R.: Dynamic representations of sparse graphs. In: Dehne, F., Gupta, A., Sack, J.-R., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 342\u2013351. Springer, Heidelberg (1999)"},{"key":"3_CR5","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546853","volume-title":"Algorithms on Strings","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Hancart, C., Lecroq, T.: Algorithms on Strings. Cambridge University Press, New York (2007)"},{"key":"3_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1007\/978-3-540-74456-6_42","volume-title":"Mathematical Foundations of Computer Science 2007","author":"M Crochemore","year":"2007","unstructured":"Crochemore, M., Ilie, L.: Analysis of maximal repetitions in strings. In: Ku\u010dera, L., Ku\u010dera, A. (eds.) MFCS 2007. LNCS, vol. 4708, pp. 465\u2013476. Springer, Heidelberg (2007)"},{"issue":"5","key":"3_CR7","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1016\/j.jcss.2007.09.003","volume":"74","author":"M Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L.: Maximal repetitions in strings. J. Comput. Syst. Sci. 74(5), 796\u2013807 (2008)","journal-title":"J. Comput. Syst. Sci."},{"key":"3_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"290","DOI":"10.1007\/978-3-540-69068-9_27","volume-title":"Combinatorial Pattern Matching","author":"M Crochemore","year":"2008","unstructured":"Crochemore, M., Ilie, L., Tinta, L.: Towards a solution to the \u201cruns\u201d conjecture. In: Ferragina, P., Landau, G.M. (eds.) CPM 2008. LNCS, vol. 5029, pp. 290\u2013302. Springer, Heidelberg (2008)"},{"key":"3_CR9","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1016\/j.tcs.2013.11.018","volume":"521","author":"M Crochemore","year":"2014","unstructured":"Crochemore, M., Iliopoulos, C.S., Kubica, M., Radoszewski, J., Rytter, W., Wale\u0144, T.: Extracting powers and periods in a word from its runs structure. Theor. Comput. Sci. 521, 29\u201341 (2014)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"277","DOI":"10.1007\/978-3-319-23826-5_27","volume-title":"String Processing and Information Retrieval","author":"J Fischer","year":"2015","unstructured":"Fischer, J., Holub, \u0160., I, T., Lewenstein, M.: Beyond the runs theorem. In: Iliopoulos, C., Puglisi, S., Yilmaz, E. (eds.) SPIRE 2015. LNCS, vol. 9309, pp. 277\u2013286. Springer, Heidelberg (2015)"},{"unstructured":"Gawrychowski, P., Kociumaka, T., Rytter, W., Wale\u0144, T.: Faster longest common extension queries in strings over general alphabets. In: Grossi, R., Lewenstein, M. (eds.) 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. LIPIcs, vol. 54, pp. 5:1\u20135:13. Schloss Dagstuhl (2016)","key":"3_CR11"},{"key":"3_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"232","DOI":"10.1007\/978-3-540-88282-4_22","volume-title":"Language and Automata Theory and Applications","author":"M Giraud","year":"2008","unstructured":"Giraud, M.: Not so many runs in strings. In: Mart\u00edn-Vide, C., Otto, F., Fernau, H. (eds.) LATA 2008. LNCS, vol. 5196, pp. 232\u2013239. Springer, Heidelberg (2008)"},{"issue":"1","key":"3_CR13","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1016\/S0304-3975(03)00099-9","volume":"307","author":"C Hohlweg","year":"2003","unstructured":"Hohlweg, C., Reutenauer, C.: Lyndon words, permutations and trees. Theor. Comput. Sci. 307(1), 173\u2013178 (2003)","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Wale\u0144, T.: Internal pattern matching queries in a text and applications. In: Indyk, P. (ed.) 26th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, pp. 532\u2013551. SIAM (2015)","key":"3_CR14","DOI":"10.1137\/1.9781611973730.36"},{"doi-asserted-by":"crossref","unstructured":"Kolpakov, R.M., Kucherov, G.: Finding maximal repetitions in a word in linear time. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pp. 596\u2013604. IEEE Computer Society (1999)","key":"3_CR15","DOI":"10.1109\/SFFCS.1999.814634"},{"unstructured":"Kolpakov, R.M., Kucherov, G.: On maximal repetitions in words. J. Discrete Algorithms, 159\u2013186. Special Issue of Matching Patterns, Hermes Science Publishing (2000). https:\/\/www.amazon.com\/Matching-Patterns-Crochemore\/dp\/190339807X","key":"3_CR16"},{"issue":"3","key":"3_CR17","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1016\/j.ipl.2015.11.016","volume":"116","author":"D Kosolobov","year":"2016","unstructured":"Kosolobov, D.: Computing runs on a general alphabet. Inf. Process. Lett. 116(3), 241\u2013244 (2016)","journal-title":"Inf. Process. Lett."},{"key":"3_CR18","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"39","author":"CSJA Nash-Williams","year":"1964","unstructured":"Nash-Williams, C.S.J.A.: Decompositions of finite graphs into forests. J. London Math. Soc. 39, 12 (1964)","journal-title":"J. London Math. Soc."},{"issue":"1\u20133","key":"3_CR19","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1016\/j.tcs.2008.04.020","volume":"401","author":"SJ Puglisi","year":"2008","unstructured":"Puglisi, S.J., Simpson, J., Smyth, W.F.: How many runs can a string contain? Theor. Comput. Sci. 401(1\u20133), 165\u2013171 (2008)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1007\/11672142_14","volume-title":"STACS 2006","author":"W Rytter","year":"2006","unstructured":"Rytter, W.: The number of runs in a string: improved analysis of the linear upper bound. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 184\u2013195. Springer, Heidelberg (2006)"},{"issue":"9","key":"3_CR21","doi-asserted-by":"crossref","first-page":"1459","DOI":"10.1016\/j.ic.2007.01.007","volume":"205","author":"W Rytter","year":"2007","unstructured":"Rytter, W.: The number of runs in a string. Inf. Comput. 205(9), 1459\u20131469 (2007)","journal-title":"Inf. Comput."}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-46049-9_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,13]],"date-time":"2019-09-13T16:13:16Z","timestamp":1568391196000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-46049-9_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319460482","9783319460499"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-46049-9_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}