{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T23:48:32Z","timestamp":1743119312701,"version":"3.40.3"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030326852"},{"type":"electronic","value":"9783030326869"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-32686-9_16","type":"book-chapter","created":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T18:02:27Z","timestamp":1570212147000},"page":"221-238","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Weighted Shortest Common Supersequence Problem Revisited"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6024-1557","authenticated-orcid":false,"given":"Panagiotis","family":"Charalampopoulos","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2477-1702","authenticated-orcid":false,"given":"Tomasz","family":"Kociumaka","sequence":"additional","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":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9162-6724","authenticated-orcid":false,"given":"Wojciech","family":"Rytter","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2207-0053","authenticated-orcid":false,"given":"Juliusz","family":"Straszy\u0144ski","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7369-3309","authenticated-orcid":false,"given":"Tomasz","family":"Wale\u0144","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1988-3507","authenticated-orcid":false,"given":"Wiktor","family":"Zuba","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,10,3]]},"reference":[{"key":"16_CR1","doi-asserted-by":"publisher","unstructured":"Abboud, A., Backurs, A., Williams, V.V.: Tight hardness results for LCS and other sequence similarity measures. In: Guruswami, V. (ed.) 56th IEEE Annual Symposium on Foundations of Computer Science, pp. 59\u201378. IEEE Computer Society (2015). \n                      https:\/\/doi.org\/10.1109\/FOCS.2015.14","DOI":"10.1109\/FOCS.2015.14"},{"issue":"5","key":"16_CR2","doi-asserted-by":"publisher","first-page":"609","DOI":"10.1109\/TKDE.2008.190","volume":"21","author":"CC Aggarwal","year":"2009","unstructured":"Aggarwal, C.C., Yu, P.S.: A survey of uncertain data algorithms and applications. IEEE Trans. Knowl. Data Eng. 21(5), 609\u2013623 (2009). \n                      https:\/\/doi.org\/10.1109\/TKDE.2008.190","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"2\u20133","key":"16_CR3","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). \n                      https:\/\/doi.org\/10.1016\/j.tcs.2008.01.006","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"16_CR4","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1016\/j.jda.2010.02.001","volume":"8","author":"A Amir","year":"2010","unstructured":"Amir, A., Gotthilf, Z., Shalom, B.R.: Weighted LCS. J. Discrete Algorithms 8(3), 273\u2013281 (2010). \n                      https:\/\/doi.org\/10.1016\/j.jda.2010.02.001","journal-title":"J. Discrete Algorithms"},{"key":"16_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"44","DOI":"10.1007\/978-3-642-24583-1_6","volume-title":"String Processing and Information Retrieval","author":"A Amir","year":"2011","unstructured":"Amir, A., Gotthilf, Z., Shalom, B.R.: Weighted shortest common supersequence. In: Grossi, R., Sebastiani, F., Silvestri, F. (eds.) SPIRE 2011. LNCS, vol. 7024, pp. 44\u201354. Springer, Heidelberg (2011). \n                      https:\/\/doi.org\/10.1007\/978-3-642-24583-1_6"},{"issue":"5","key":"16_CR6","doi-asserted-by":"publisher","first-page":"1755","DOI":"10.1137\/17M1158203","volume":"47","author":"N Bansal","year":"2018","unstructured":"Bansal, N., Garg, S., Nederlof, J., Vyas, N.: Faster space-efficient algorithms for subset sum, \n                      \n                        \n                      \n                      $$k$$\n                    -sum, and related problems. SIAM J. Comput. 47(5), 1755\u20131777 (2018). \n                      https:\/\/doi.org\/10.1137\/17M1158203","journal-title":"SIAM J. Comput."},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Barton, C., Kociumaka, T., Liu, C., Pissis, S.P., Radoszewski, J.: Indexing weighted sequences: neat and efficient. Inf. Comput. (2019). \n                      https:\/\/doi.org\/10.1016\/j.ic.2019.104462","DOI":"10.1016\/j.ic.2019.104462"},{"key":"16_CR8","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.) 27th Annual Symposium on Combinatorial Pattern Matching, CPM 2016. LIPIcs, vol. 54, pp. 4:1\u20134:13. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2016). \n                      https:\/\/doi.org\/10.4230\/LIPIcs.CPM.2016.4","DOI":"10.4230\/LIPIcs.CPM.2016.4"},{"key":"16_CR9","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). \n                      https:\/\/doi.org\/10.1016\/j.tcs.2016.04.029","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"16_CR10","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1007\/s00453-016-0266-0","volume":"80","author":"C Barton","year":"2018","unstructured":"Barton, C., Pissis, S.P.: Crochemore\u2019s partitioning on weighted strings and applications. Algorithmica 80(2), 496\u2013514 (2018). \n                      https:\/\/doi.org\/10.1007\/s00453-016-0266-0","journal-title":"Algorithmica"},{"key":"16_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-319-77404-6_22","volume-title":"LATIN 2018: Theoretical Informatics","author":"P Charalampopoulos","year":"2018","unstructured":"Charalampopoulos, P., Iliopoulos, C.S., Liu, C., Pissis, S.P.: Property suffix array with applications. In: Bender, M.A., Farach-Colton, M., Mosteiro, M.A. (eds.) LATIN 2018. LNCS, vol. 10807, pp. 290\u2013302. Springer, Cham (2018). \n                      https:\/\/doi.org\/10.1007\/978-3-319-77404-6_22"},{"key":"16_CR12","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.ic.2019.01.001","volume":"266","author":"P Charalampopoulos","year":"2019","unstructured":"Charalampopoulos, P., Iliopoulos, C.S., Pissis, S.P., Radoszewski, J.: On-line weighted pattern matching. Inf. Comput. 266, 49\u201359 (2019). \n                      https:\/\/doi.org\/10.1016\/j.ic.2019.01.001","journal-title":"Inf. Comput."},{"key":"16_CR13","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. MIT Press (2009). \n                      https:\/\/mitpress.mit.edu\/books\/introduction-algorithms-third-edition"},{"key":"16_CR14","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., Wale\u0144, T.: Polynomial-time approximation algorithms for weighted LCS problem. Discrete Appl. Math. 204, 38\u201348 (2016). \n                      https:\/\/doi.org\/10.1016\/j.dam.2015.11.011","journal-title":"Discrete Appl. Math."},{"issue":"2","key":"16_CR15","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). \n                      https:\/\/doi.org\/10.1145\/321812.321823","journal-title":"J. ACM"},{"issue":"2","key":"16_CR16","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 \n                      \n                        \n                      \n                      $$k$$\n                    -SAT. J. Comput. Syst. Sci. 62(2), 367\u2013375 (2001). \n                      https:\/\/doi.org\/10.1006\/jcss.2000.1727","journal-title":"J. Comput. Syst. Sci."},{"issue":"4","key":"16_CR17","doi-asserted-by":"publisher","first-page":"512","DOI":"10.1006\/jcss.2001.1774","volume":"63","author":"R Impagliazzo","year":"2001","unstructured":"Impagliazzo, R., Paturi, R., Zane, F.: Which problems have strongly exponential complexity? J. Comput. Syst. Sci. 63(4), 512\u2013530 (2001). \n                      https:\/\/doi.org\/10.1006\/jcss.2001.1774","journal-title":"J. Comput. Syst. Sci."},{"issue":"5","key":"16_CR18","doi-asserted-by":"publisher","first-page":"1122","DOI":"10.1137\/S009753979223842X","volume":"24","author":"T Jiang","year":"1995","unstructured":"Jiang, T., Li, M.: On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput. 24(5), 1122\u20131139 (1995). \n                      https:\/\/doi.org\/10.1137\/S009753979223842X","journal-title":"SIAM J. Comput."},{"key":"16_CR19","doi-asserted-by":"publisher","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Miller, R.E., Thatcher, J.W. (eds.) Symposium on the Complexity of Computer Computations. pp. 85\u2013103. The IBM Research Symposia Series, Plenum Press, New York (1972). \n                      https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"16_CR20","unstructured":"Kipouridis, E., Tsichlas, K.: Longest common subsequence on weighted sequences (2019). \n                      http:\/\/arxiv.org\/abs\/1901.04068"},{"issue":"3","key":"16_CR21","doi-asserted-by":"publisher","first-page":"506","DOI":"10.1007\/s00224-018-9881-2","volume":"63","author":"T Kociumaka","year":"2019","unstructured":"Kociumaka, T., Pissis, S.P., Radoszewski, J.: Pattern matching and consensus problems on weighted sequences and profiles. Theory Comput. Syst. 63(3), 506\u2013542 (2019). \n                      https:\/\/doi.org\/10.1007\/s00224-018-9881-2","journal-title":"Theory Comput. Syst."},{"key":"16_CR22","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. Bull. EATCS 105, 41\u201372 (2011). \n                      http:\/\/eatcs.org\/beatcs\/index.php\/beatcs\/article\/view\/92","journal-title":"Bull. EATCS"},{"issue":"2","key":"16_CR23","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1145\/322063.322075","volume":"25","author":"D Maier","year":"1978","unstructured":"Maier, D.: The complexity of some problems on subsequences and supersequences. J. ACM 25(2), 322\u2013336 (1978). \n                      https:\/\/doi.org\/10.1145\/322063.322075","journal-title":"J. ACM"},{"key":"16_CR24","doi-asserted-by":"publisher","unstructured":"Radoszewski, J., Starikovskaya, T.: Streaming \n                      \n                        \n                      \n                      $$k$$\n                    -mismatch with error correcting and applications. In: Bilgin, A., Marcellin, M.W., Serra-Sagrist\u00e0, J., Storer, J.A. (eds.) Data Compression Conference, DCC 2017, pp. 290\u2013299. IEEE (2017). \n                      https:\/\/doi.org\/10.1109\/DCC.2017.14","DOI":"10.1109\/DCC.2017.14"},{"key":"16_CR25","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1016\/0304-3975(81)90075-X","volume":"16","author":"K R\u00e4ih\u00e4","year":"1981","unstructured":"R\u00e4ih\u00e4, K., Ukkonen, E.: The shortest common supersequence problem over binary alphabet is NP-complete. Theor. Comput. Sci. 16, 187\u2013198 (1981). \n                      https:\/\/doi.org\/10.1016\/0304-3975(81)90075-X","journal-title":"Theor. Comput. Sci."},{"key":"16_CR26","doi-asserted-by":"publisher","unstructured":"Stormo, G.D., Schneider, T.D., Gold, L., Ehrenfeucht, A.: Use of the \u2018perceptron\u2019 algorithm to distinguish translational initiation sites in E. coli. Nucl. Acids Res. 10(9), 2997\u20133011 (1982). \n                      https:\/\/doi.org\/10.1093\/nar\/10.9.2997","DOI":"10.1093\/nar\/10.9.2997"}],"container-title":["Lecture Notes in Computer Science","String Processing and Information Retrieval"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-32686-9_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,4]],"date-time":"2019-10-04T21:06:58Z","timestamp":1570223218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-32686-9_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030326852","9783030326869"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-32686-9_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"3 October 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SPIRE","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Symposium on String Processing and Information Retrieval","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Segovia","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Spain","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"7 October 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"9 October 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"spire2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/spire19.lbd.org.es\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"59","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"8","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"47% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"1","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}