{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:12:00Z","timestamp":1760202720344,"version":"3.37.3"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,1,27]],"date-time":"2017-01-27T00:00:00Z","timestamp":1485475200000},"content-version":"unspecified","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":[[2018,2]]},"DOI":"10.1007\/s00453-016-0266-0","type":"journal-article","created":{"date-parts":[[2017,1,27]],"date-time":"2017-01-27T09:06:17Z","timestamp":1485507977000},"page":"496-514","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Crochemore\u2019s Partitioning on Weighted Strings and Applications"],"prefix":"10.1007","volume":"80","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1589-0432","authenticated-orcid":false,"given":"Carl","family":"Barton","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,1,27]]},"reference":[{"key":"266_CR1","doi-asserted-by":"publisher","first-page":"2","DOI":"10.1016\/j.dam.2015.05.019","volume":"212","author":"A Alatabbi","year":"2016","unstructured":"Alatabbi, A., Rahman, M.S., Smyth, W.F.: Computing covers using prefix tables. Dis. Appl. Math. 212, 2\u20139 (2016). doi: 10.1016\/j.dam.2015.05.019","journal-title":"Dis. Appl. Math."},{"issue":"2\u20133","key":"266_CR2","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1016\/j.tcs.2008.01.006","volume":"395","author":"A Amir","year":"2008","unstructured":"Amir, A., Chencinski, E., Iliopoulos, C.S., Kopelowitz, T., Zhang, H.: Property matching and weighted matching. Theor. Comput. Sci. 395(2\u20133), 298\u2013310 (2008). doi: 10.1016\/j.tcs.2008.01.006","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"266_CR3","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1016\/0020-0190(91)90056-N","volume":"39","author":"A Apostolico","year":"1991","unstructured":"Apostolico, A., Farach, M., Iliopoulos, C.S.: Optimal superprimitivity testing for strings. Inf. Process. Lett 39(1), 17\u201320 (1991)","journal-title":"Inf. Process. Lett"},{"key":"266_CR4","unstructured":"Bannai, H., I, T., Inenaga, S., Nakashima, Y., Takeda, M., Tsuruta, K.: The \u201cruns\u201d theorem. arXiv:1406.0263v7 (2014). URL http:\/\/arxiv.org\/abs\/1406.0263"},{"key":"266_CR5","doi-asserted-by":"publisher","unstructured":"Barton, C., Iliopoulos, C., Pissis, S.: Optimal computation of all tandem repeats in a weighted sequence. Algorithms Mol. Biol. 9, (2014). doi: 10.1186\/s13015-014-0021-5","DOI":"10.1186\/s13015-014-0021-5"},{"key":"266_CR6","doi-asserted-by":"publisher","unstructured":"Barton, C., Kociumaka, T., Pissis, S.P., Radoszewski, J.: Efficient index for weighted sequences. In: R.\u00a0Grossi, M.\u00a0Lewenstein (eds.) 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016), Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a054, pp. 4:1\u20134:13. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). doi: 10.4230\/LIPIcs.CPM.2016.4","DOI":"10.4230\/LIPIcs.CPM.2016.4"},{"key":"266_CR7","doi-asserted-by":"publisher","unstructured":"Barton, C., Liu, C., Pissis, S.P.: Linear-time computation of prefix table for weighted strings & applications. Theor. Comput. Sci. 656(Part B), 160\u2013172 (2016).doi: 10.1016\/j.tcs.2016.04.029 . Stringology: In Celebration of Bill Smyth\u2019s 80th Birthday","DOI":"10.1016\/j.tcs.2016.04.029"},{"key":"266_CR8","doi-asserted-by":"publisher","unstructured":"Barton, C., Liu, C., Pissis, S.P.: On-line pattern matching on uncertain sequences and applications. In: T.H. Chan, M.\u00a0Li, L.\u00a0Wang (eds.) Combinatorial Optimization and Applications\u201410th International Conference, COCOA 2016, Hong Kong, China, 16\u201318 Dec, 2016, Proceedings. Lecture Notes in Computer Science, vol. 10043, pp. 547\u2013562. Springer (2016). doi: 10.1007\/978-3-319-48749-6_40","DOI":"10.1007\/978-3-319-48749-6_40"},{"key":"266_CR9","doi-asserted-by":"publisher","unstructured":"Bender, M.A., Farach-Colton, M.: The LCA problem revisited. In: G.H. Gonnet, D.\u00a0Panario, A.\u00a0Viola (eds.) LATIN 2000: Theoretical Informatics, 4th Latin American Symposium, Punta del Este, Uruguay, 10\u201314 Apr, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1776, pp. 88\u201394. Springer (2000). doi: 10.1007\/10719839_9","DOI":"10.1007\/10719839_9"},{"issue":"6","key":"266_CR10","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/0020-0190(92)90111-8","volume":"44","author":"D Breslauer","year":"1992","unstructured":"Breslauer, D.: An on-line string superprimitivity test. Inf. Process. Lett 44(6), 345\u2013347 (1992)","journal-title":"Inf. Process. Lett"},{"key":"266_CR11","doi-asserted-by":"publisher","unstructured":"Brodal, G.S., Pedersen, C.N.S.: Finding maximal quasiperiodicities in strings. In: R.\u00a0Giancarlo, D.\u00a0Sankoff (eds.) Combinatorial Pattern Matching, 11th Annual Symposium, CPM 2000, Montreal, Canada, 21\u201323 June, 2000, Proceedings. Lecture Notes in Computer Science, vol. 1848, pp. 397\u2013411. Springer (2000). doi: 10.1007\/3-540-45123-4_33","DOI":"10.1007\/3-540-45123-4_33"},{"issue":"6","key":"266_CR12","doi-asserted-by":"crossref","first-page":"1214","DOI":"10.1089\/cmb.2006.13.1214","volume":"13","author":"M Christodoulakis","year":"2006","unstructured":"Christodoulakis, M., Iliopoulos, C.S., Mouchard, L., Perdikuri, K., Tsakalidis, A.K., Tsichlas, K.: Computation of repetitions and regularities of biologically weighted sequences. J. Comput. Biol. 13(6), 1214\u20131231 (2006)","journal-title":"J. Comput. Biol."},{"issue":"5","key":"266_CR13","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0020-0190(81)90024-7","volume":"12","author":"M Crochemore","year":"1981","unstructured":"Crochemore, M.: An optimal algorithm for computing the repetitions in a word. Inf. Process. Lett. 12(5), 244\u2013250 (1981). doi: 10.1016\/0020-0190(81)90024-7","journal-title":"Inf. Process. Lett."},{"key":"266_CR14","doi-asserted-by":"publisher","unstructured":"Crochemore, M., Iliopoulos, C.S., Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: Covering problems for partial words and for indeterminate strings. In: H.\u00a0Ahn, C.\u00a0Shin (eds.) Algorithms and Computation\u201425th International Symposium, ISAAC 2014, Jeonju, Korea, 15\u201317 Dec 2014, Proceedings. Lecture Notes in Computer Science, vol. 8889, pp. 220\u2013232. Springer (2014). doi: 10.1007\/978-3-319-13075-0_18","DOI":"10.1007\/978-3-319-13075-0_18"},{"key":"266_CR15","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.dam.2015.11.011","volume":"204","author":"M Cygan","year":"2016","unstructured":"Cygan, M., Kubica, M., Radoszewski, J., Rytter, W., Walen, T.: Polynomial-time approximation algorithms for weighted LCS problem. Dis. Appl. Math. 204, 38\u201348 (2016). doi: 10.1016\/j.dam.2015.11.011","journal-title":"Dis. Appl. Math."},{"key":"266_CR16","doi-asserted-by":"publisher","first-page":"102","DOI":"10.1016\/j.tcs.2013.08.013","volume":"506","author":"T Flouri","year":"2013","unstructured":"Flouri, T., Iliopoulos, C.S., Kociumaka, T., Pissis, S.P., Puglisi, S.J., Smyth, W.F., Tyczynski, W.: Enhanced string covering. Theor. Comput. Sci. 506, 102\u2013114 (2013). doi: 10.1016\/j.tcs.2013.08.013","journal-title":"Theor. Comput. Sci."},{"key":"266_CR17","unstructured":"Franek, F., Jiang, M., Weng, C.: An improved version of the runs algorithm based on crochemore\u2019s partitioning algorithm. In: Holub, J., Zd\u00e1rek, J. (eds.) Proceedings of the Prague Stringology Conference 2011, Prague, Czech Republic, 29\u201331 Aug 2011, pp. 98\u2013105. Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague Stringology Club (2011)"},{"issue":"34\u201336","key":"266_CR18","doi-asserted-by":"publisher","first-page":"3110","DOI":"10.1016\/j.tcs.2010.04.039","volume":"411","author":"R Groult","year":"2010","unstructured":"Groult, R., Richomme, G.: Optimality of some algorithms to detect quasiperiodicities. Theor. Comput. Sci. 411(34\u201336), 3110\u20133122 (2010). doi: 10.1016\/j.tcs.2010.04.039","journal-title":"Theor. Comput. Sci."},{"issue":"2,3","key":"266_CR19","first-page":"259","volume":"71","author":"CS Iliopoulos","year":"2006","unstructured":"Iliopoulos, C.S., Makris, C., Panagis, Y., Perdikuri, K., Theodoridis, E., Tsakalidis, A.: The weighted suffix tree: an efficient data structure for handling molecular weighted sequences and its applications. Fundam. Inf. 71(2,3), 259\u2013277 (2006)","journal-title":"Fundam. Inf."},{"key":"266_CR20","unstructured":"Iliopoulos, C.S., Mouchard, L.: Fast local covers. Technical Report TR98-03 (1998)"},{"issue":"3","key":"266_CR21","first-page":"213","volume":"4","author":"CS Iliopoulos","year":"1999","unstructured":"Iliopoulos, C.S., Mouchard, L.: Quasiperiodicity: from detection to normal forms. J. Autom., Lang. Comb. 4(3), 213\u2013228 (1999)","journal-title":"J. Autom., Lang. Comb."},{"issue":"5\/6","key":"266_CR22","first-page":"687","volume":"10","author":"CS Iliopoulos","year":"2005","unstructured":"Iliopoulos, C.S., Mouchard, L., Perdikuri, K., Tsakalidis, A.K.: Computing the repetitions in a biological weighted sequence. J. Autom., Lang. Comb. 10(5\/6), 687\u2013696 (2005)","journal-title":"J. Autom., Lang. Comb."},{"key":"266_CR23","doi-asserted-by":"publisher","unstructured":"Kociumaka, T., Pissis, S.P., Radoszewski, J.: Pattern matching and consensus problems on weighted sequences and profiles. In: S.H. Hong (ed.) 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), vol.\u00a064, pp. 46:1\u201346:12. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2016). doi: 10.4230\/LIPIcs.ISAAC.2016.46","DOI":"10.4230\/LIPIcs.ISAAC.2016.46"},{"key":"266_CR24","doi-asserted-by":"publisher","unstructured":"Kociumaka, T., Radoszewski, J., Rytter, W., Walen, T.: Efficient data structures for the factor periodicity problem. In: L.\u00a0Calder\u00f3n-Benavides, C.N. Gonz\u00e1lez-Caro, E.\u00a0Ch\u00e1vez, N.\u00a0Ziviani (eds.) String Processing and Information Retrieval\u201419th International Symposium, SPIRE 2012, Cartagena de Indias, Colombia, 21\u201325 Oct 2012. Proceedings. Lecture Notes in Computer Science, vol. 7608, pp. 284\u2013294. Springer (2012). doi: 10.1007\/978-3-642-34109-0_30","DOI":"10.1007\/978-3-642-34109-0_30"},{"key":"266_CR25","doi-asserted-by":"publisher","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 \u201999, 17\u201318 Oct, 1999, New York, NY, USA, pp. 596\u2013604. IEEE Computer Society (1999). doi: 10.1109\/SFFCS.1999.814634","DOI":"10.1109\/SFFCS.1999.814634"},{"issue":"1","key":"266_CR26","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/s00453-001-0062-2","volume":"32","author":"Y Li","year":"2002","unstructured":"Li, Y., Smyth, W.F.: Computing the cover array in linear time. Algorithmica 32(1), 95\u2013106 (2002). doi: 10.1007\/s00453-001-0062-2","journal-title":"Algorithmica"},{"issue":"3","key":"266_CR27","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1016\/0196-6774(84)90021-X","volume":"5","author":"MG Main","year":"1984","unstructured":"Main, M.G., Lorentz, R.J.: An $${O}(n \\log n)$$ O ( n log n ) algorithm for finding all repetitions in a string. J. Algorithms 5(3), 422\u2013432 (1984). doi: 10.1016\/0196-6774(84)90021-X","journal-title":"J. Algorithms"},{"issue":"5","key":"266_CR28","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1016\/0020-0190(94)00045-X","volume":"50","author":"D Moore","year":"1994","unstructured":"Moore, D., Smyth, W.F.: An optimal algorithm to compute all the covers of a string. Inf. Process. Lett. 50(5), 239\u2013246 (1994). doi: 10.1016\/0020-0190(94)00045-X","journal-title":"Inf. Process. Lett."},{"key":"266_CR29","doi-asserted-by":"crossref","unstructured":"Nomenclature Committee of the International Union of Biochemistry: (NC-IUB): Nomenclature for incompletely specified bases in nucleic acid sequences. Recommendations 1984. Eur. J. Biochem. 150(1), 1\u20135 (1985)","DOI":"10.1111\/j.1432-1033.1985.tb08977.x"},{"issue":"9","key":"266_CR30","doi-asserted-by":"publisher","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). doi: 10.1016\/j.ic.2007.01.007","journal-title":"Inf. Comput."},{"key":"266_CR31","doi-asserted-by":"publisher","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: Varieties of regularities in weighted sequences. In: B.\u00a0Chen (ed.) Algorithmic Aspects in Information and Management, 6th International Conference, AAIM 2010, Weihai, China, 19\u201321 July, 2010. Proceedings. Lecture Notes in Computer Science, vol. 6124, pp. 271\u2013280. Springer (2010). doi: 10.1007\/978-3-642-14355-7_28","DOI":"10.1007\/978-3-642-14355-7_28"},{"issue":"S\u20138","key":"266_CR32","doi-asserted-by":"crossref","first-page":"S2","DOI":"10.1186\/1471-2105-14-S8-S2","volume":"14","author":"H Zhang","year":"2013","unstructured":"Zhang, H., Guo, Q., Iliopoulos, C.S.: Locating tandem repeats in weighted sequences in proteins. BMC Bioinform. 14(S\u20138), S2 (2013)","journal-title":"BMC Bioinform."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-016-0266-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-0266-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-016-0266-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,17]],"date-time":"2019-09-17T21:32:46Z","timestamp":1568755966000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-016-0266-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,27]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,2]]}},"alternative-id":["266"],"URL":"https:\/\/doi.org\/10.1007\/s00453-016-0266-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2017,1,27]]}}}