{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,9]],"date-time":"2026-02-09T20:06:36Z","timestamp":1770667596264,"version":"3.49.0"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T00:00:00Z","timestamp":1533859200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001870","name":"Fundacja na rzecz Nauki Polskiej","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001870","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2019,4]]},"DOI":"10.1007\/s00224-018-9881-2","type":"journal-article","created":{"date-parts":[[2018,8,10]],"date-time":"2018-08-10T07:15:19Z","timestamp":1533885319000},"page":"506-542","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Pattern Matching and Consensus Problems on Weighted Sequences and Profiles"],"prefix":"10.1007","volume":"63","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1445-1932","authenticated-orcid":false,"given":"Solon P.","family":"Pissis","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0067-6401","authenticated-orcid":false,"given":"Jakub","family":"Radoszewski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,8,10]]},"reference":[{"issue":"2-3","key":"9881_CR1","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-3), 298\u2013310 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.01.006","journal-title":"Theor. Comput. Sci."},{"key":"9881_CR2","doi-asserted-by":"publisher","unstructured":"Barton, C., Kociumaka, T., Pissis, S. P., Radoszewski, J.: Efficient index for weighted sequences. In: Grossi, R., Lewenstein, M. (eds.) Combinatorial Pattern Matching, CPM 2016, LIPIcs, vol. 54, pp. 4:1\u20134:13. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2016.4 . Dagstuhl, Germany (2016)","DOI":"10.4230\/LIPIcs.CPM.2016.4"},{"key":"9881_CR3","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.tcs.2016.04.029","volume":"656","author":"C Barton","year":"2016","unstructured":"Barton, C., Liu, C., Pissis, S. P.: Linear-time computation of prefix table for weighted strings & applications. Theor. Comput. Sci. 656, 160\u2013172 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.04.029","journal-title":"Theor. Comput. Sci."},{"key":"9881_CR4","doi-asserted-by":"publisher","unstructured":"Barton, C., Liu, C., Pissis, S. P.: On-line pattern matching on uncertain sequences and applications. In: Chan, T.H., Li, M., Wang, L. (eds.) Combinatorial optimization and applications, COCOA 2016, LNCS, vol. 10043, pp. 547\u2013562. https:\/\/doi.org\/10.1007\/978-3-319-48749-6_40 . Springer, Berlin (2016)","DOI":"10.1007\/978-3-319-48749-6_40"},{"key":"9881_CR5","doi-asserted-by":"crossref","unstructured":"Barton, C., Liu, C., Pissis, S.P.: Fast average-case pattern matching on weighted sequences. To appear in the International Journal of Foundations of Computer Science (2017)","DOI":"10.1142\/S0129054118430062"},{"key":"9881_CR6","doi-asserted-by":"publisher","unstructured":"Biswas, S., Patil, M., Thankachan, S. V., Shah, R.: Probabilistic threshold indexing for uncertain strings. In: E. Pitoura, S. Maabout, G. Koutrika, A. Marian, L. Tanca, I. Manolescu, K. Stefanidis (eds.) 19th International Conference on Extending Database Technology, EDBT 2016, pp. 401\u2013412. OpenProceedings.org. https:\/\/doi.org\/10.5441\/002\/edbt.2016.37 (2016)","DOI":"10.5441\/002\/edbt.2016.37"},{"key":"9881_CR7","unstructured":"Christodoulakis, M., Iliopoulos, C. S., Mouchard, L., Tsichlas, K.: Pattern matching on weighted sequences. In: Algorithms and Computational Methods for Biochemical and Evolutionary Networks, CompBioNets 2004, KCL publications (2004)"},{"key":"9881_CR8","doi-asserted-by":"publisher","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, Cambridge (2007). https:\/\/doi.org\/10.1017\/cbo9780511546853"},{"key":"9881_CR9","doi-asserted-by":"publisher","unstructured":"Etscheid, M., Kratsch, S., Mnich, M., R\u00f6glin, H.: Polynomial kernels for weighted problems. In: G.F. Italiano, G. Pighizzini, D. Sannella (eds.) Mathematical Foundations of Computer Science, MFCS 2015, Part II, LNCS, vol. 9235, pp. 287\u2013298. Springer. https:\/\/doi.org\/10.1007\/978-3-662-48054-0_24 (2015)","DOI":"10.1007\/978-3-662-48054-0_24"},{"key":"9881_CR10","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0925-7721(95)00022-2","volume":"5","author":"A Gajentaan","year":"1995","unstructured":"Gajentaan, A., Overmars, M. H.: On a class of O(n 2) problems in computational geometry. Comput. Geom. 5, 165\u2013185 (1995). https:\/\/doi.org\/10.1016\/0925-7721(95)00022-2","journal-title":"Comput. Geom."},{"key":"9881_CR11","unstructured":"Gurari, E. M.: Introduction to the theory of computation. Computer Science Press (1989)"},{"issue":"2","key":"9881_CR12","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1145\/321812.321823","volume":"21","author":"E Horowitz","year":"1974","unstructured":"Horowitz, E., Sahni, S.: Computing partitions with applications to the knapsack problem. J. ACM, 21(2), 277\u2013292 (1974). https:\/\/doi.org\/10.1145\/321812.321823","journal-title":"J. ACM,"},{"issue":"2-3","key":"9881_CR13","doi-asserted-by":"crossref","first-page":"259","DOI":"10.3233\/FUN-2006-712-307","volume":"71","author":"CS Iliopoulos","year":"2006","unstructured":"Iliopoulos, C.S., Makris, C., Panagis, Y., Perdikuri, K., Theodoridis, E., Tsakalidis, A.K.: The weighted suffix tree: An efficient data structure for handling molecular weighted sequences and its applications. Fundamenta Informaticae 71 (2-3), 259\u2013277 (2006). http:\/\/content.iospress.com\/articles\/fundamenta-informaticae\/fi71-2-3-07","journal-title":"Fundamenta Informaticae"},{"issue":"6","key":"9881_CR14","doi-asserted-by":"publisher","first-page":"218","DOI":"10.1016\/j.ipl.2007.09.004","volume":"105","author":"CS Iliopoulos","year":"2008","unstructured":"Iliopoulos, C. S., Rahman, M. S.: Faster index for property matching. Inf. Process. Lett. 105(6), 218\u2013223 (2008). https:\/\/doi.org\/10.1016\/j.ipl.2007.09.004","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9881_CR15","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1006\/jcss.2000.1727","volume":"62","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R.: On the complexity of k-SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"18","key":"9881_CR16","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1016\/j.ipl.2009.06.009","volume":"109","author":"MT Juan","year":"2009","unstructured":"Juan, M. T., Liu, J. J., Wang, Y. L.: Errata for \u201cFaster index for property matching\u201d. Inf. Process. Lett. 109(18), 1027\u20131029 (2009). https:\/\/doi.org\/10.1016\/j.ipl.2009.06.009","journal-title":"Inf. Process. Lett."},{"key":"9881_CR17","doi-asserted-by":"publisher","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack problems. Springer. https:\/\/doi.org\/10.1007\/978-3-540-24777-7 (2004)","DOI":"10.1007\/978-3-540-24777-7"},{"key":"9881_CR18","doi-asserted-by":"publisher","unstructured":"Kociumaka, T., Pissis, S. P., Radoszewski, J.: Pattern matching and consensus problems on weighted sequences and profiles. In: S. Hong (ed.) Algorithms and Computation, ISAAC 2016, LIPIcs, vol. 64, pp. 46:1\u201346:12. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik. https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2016.46 (2016)","DOI":"10.4230\/LIPIcs.ISAAC.2016.46"},{"key":"9881_CR19","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1016\/j.tcs.2016.02.033","volume":"638","author":"T Kopelowitz","year":"2016","unstructured":"Kopelowitz, T.: The property suffix tree with dynamic properties. Theor. Comput. Sci. 638, 44\u201351 (2016). https:\/\/doi.org\/10.1016\/j.tcs.2016.02.033","journal-title":"Theor. Comput. Sci."},{"key":"9881_CR20","first-page":"41","volume":"105","author":"D Lokshtanov","year":"2011","unstructured":"Lokshtanov, D., Marx, D., Saurabh, S.: Lower bounds based on the Exponential Time Hypothesis. Bulletin of the EATCS 105, 41\u201372 (2011). http:\/\/bulletin.eatcs.org\/index.php\/beatcs\/article\/view\/92","journal-title":"Bulletin of the EATCS"},{"key":"9881_CR21","doi-asserted-by":"publisher","first-page":"287","DOI":"10.1007\/BF00264563","volume":"5","author":"K Mehlhorn","year":"1975","unstructured":"Mehlhorn, K.: Nearly optimal binary search trees. Acta Inform. 5, 287\u2013295 (1975). https:\/\/doi.org\/10.1007\/BF00264563","journal-title":"Acta Inform."},{"issue":"2-3","key":"9881_CR22","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1016\/j.tcs.2008.01.015","volume":"395","author":"C Pizzi","year":"2008","unstructured":"Pizzi, C., Ukkonen, E.: Fast profile matching algorithms - A survey. Theor. Comput. Sci. 395(2-3), 137\u2013157 (2008). https:\/\/doi.org\/10.1016\/j.tcs.2008.01.015","journal-title":"Theor. Comput. Sci."},{"key":"9881_CR23","doi-asserted-by":"publisher","unstructured":"Radoszewski, J., Starikovskaya, T. A.: Streaming k-mismatch with error correcting and applications. In: A. Bilgin, M.W. Marcellin, J. Serra-Sagrista\u0307, J.A. Storer (eds.) Data Compression Conference, DCC 2017, pp. 290\u2013299. IEEE. https:\/\/doi.org\/10.1109\/DCC.2017.14 (2017)","DOI":"10.1109\/DCC.2017.14"},{"issue":"1","key":"9881_CR24","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1089\/10665270252833172","volume":"9","author":"S Rajasekaran","year":"2002","unstructured":"Rajasekaran, S., Jin, X., Spouge, J. L.: The efficient computation of position-specific match scores with the fast Fourier transform. J. Comput. Biol. 9(1), 23\u201333 (2002). https:\/\/doi.org\/10.1089\/10665270252833172","journal-title":"J. Comput. Biol."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9881-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-018-9881-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-018-9881-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,6]],"date-time":"2025-07-06T08:32:26Z","timestamp":1751790746000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-018-9881-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,8,10]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,4]]}},"alternative-id":["9881"],"URL":"https:\/\/doi.org\/10.1007\/s00224-018-9881-2","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,8,10]]},"assertion":[{"value":"10 August 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}