{"entities":{"Q1736579":{"pageid":1747320,"ns":120,"title":"Item:Q1736579","lastrevid":56713518,"modified":"2026-03-19T03:16:03Z","type":"item","id":"Q1736579","labels":{"en":{"language":"en","value":"A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7042174"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$05CD9C5D-C247-416C-A8EF-6B6697535538","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c82073405eaac1ae7014057ec8853f2aeb347ae7","datavalue":{"value":{"text":"A simple algorithm for solving for the generalized longest common subsequence (LCS) problem with a substring exclusion constraint","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1736579$1503B081-77B4-4E1D-B70F-68A4715BFE8E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"28a352173307a928a76d54e3ec8e0eed83c66f0d","datavalue":{"value":"1461.68273","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$8A141C68-C696-44AF-88DA-D0DC7B56C2F5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"d549399ff9d3dc8cccd728bb7d0777be4daceb74","datavalue":{"value":{"entity-type":"item","numeric-id":207894,"id":"Q207894"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$6F70F913-42F9-4521-A00F-B61B5135B639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ded25cd890e9005b337b1072aaef05ea64eb883f","datavalue":{"value":{"entity-type":"item","numeric-id":1622423,"id":"Q1622423"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$6890CF3C-F4B4-43EB-82D2-BAF4E8EAB961","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$FBC516F5-0034-432A-9AD8-83EF1C36FFFD","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d660e31d569d3203bec6d5e897b7f6ed7f6a3a72","datavalue":{"value":{"time":"+2019-03-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1736579$5AA11A46-BD3B-47DF-BC5E-9AB06795C46D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"1a4262e2b328491e102e0bc6b446b022ee2d75f4","datavalue":{"value":"Summary: This paper studies the string-excluding (STR-EC)-constrained longest common subsequence (LCS) problem, a generalized LCS problem. For the two input sequences, \\(X\\) and \\(Y\\), of lengths \\(n\\) and \\(m\\) and a constraint string, \\(P\\), of length \\(r\\), the goal is to find the longest common subsequence, \\(Z\\), of \\(X\\) and \\(Y\\) that excludes \\(P\\) as a substring. The problem and its solution were first proposed by \\textit{Y.-C. Chen} and \\textit{K.-M. Chao} [J. Comb. Optim. 21, No. 3, 383--392 (2011; Zbl 1319.68263)], but we found that their algorithm cannot solve the problem correctly. A new dynamic programming solution for the STR-EC-LCS problem is then presented in this paper, and the correctness of the new algorithm is proven. The time complexity of the new algorithm is \\(O(nmr)\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736579$EFC54968-C485-480A-86AF-B00F8DAF83EE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$3F4CDDC4-C32F-4B3D-8190-614ABC5BB901","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$A1E3C89A-B89C-47DA-8276-FA30A7735887","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"aa3ca91474fff28e420d9cace433f8447ec799b0","datavalue":{"value":"90C39","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$5AA28C88-6A85-4D1B-BD08-BEEF49877840","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"ecaa310d4585e2ec41feb436b827ebc1dee4e2eb","datavalue":{"value":"7042174","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$0FE8F8A1-E4EB-4D57-A21F-12C37E352A94","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2a7d58fff80ea25d513d1ec955478d399bd163e2","datavalue":{"value":"constrained LCS","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736579$4E21AB53-EF0B-4F66-9447-50F421D91896","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aede851d5da41a8d81114d705f3b5265a7cb7cd2","datavalue":{"value":"string-excluding","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736579$F42F6DE9-BC80-4E31-91AE-E5583BA5BE5D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0d82cfa81638332a8c825bcbbd9d7f7f9c0c45be","datavalue":{"value":"dynamic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q1736579$985842D7-FF38-4C06-8A56-C4883A3BDAA5","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$8469E723-C6E6-4A25-8DBC-2939620979D1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e5ca56c9b770a1e69b6fcdf6e8b9a1d58d3465db","datavalue":{"value":"https://doi.org/10.3390/a6030485","type":"string"},"datatype":"url"},"type":"statement","id":"Q1736579$53F4BF12-E7C3-4C10-BF83-AE05BC488FE3","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"fce009bb6caf1e922f72d5a3552fc371c7f0c9f7","datavalue":{"value":"W2052437266","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$D2E62469-02BB-449E-8E7A-BC28179E8A1A","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1d677d20d8bd6c2f159dd8ab44b0da6ec7697e3d","datavalue":{"value":{"entity-type":"item","numeric-id":1029006,"id":"Q1029006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$CB1DC08C-4070-4CC8-8432-134A258252D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3abcb098512d9227f423fdfdc304ceabb06c3f04","datavalue":{"value":{"entity-type":"item","numeric-id":2970219,"id":"Q2970219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$3C882AF2-8797-42F0-A737-074A0C9D4413","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"919013614ddece9cc904fc805d6cab7e06acd390","datavalue":{"value":{"entity-type":"item","numeric-id":733720,"id":"Q733720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$889D2030-E944-4120-B648-86E7846617F2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d5b381bd48ad949a6bdf7f2a791e9e9201abd63f","datavalue":{"value":{"entity-type":"item","numeric-id":5187851,"id":"Q5187851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$5DD8DB35-FBCD-486D-847E-BE27D1C04800","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"266aeb150c8fd6e8b7d4cd0daf02e8ff749120b1","datavalue":{"value":{"entity-type":"item","numeric-id":491203,"id":"Q491203"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$AF75AA27-D4F0-4189-A97C-CB16B2CE4F6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cac7f741f9b1e3426d597355d63b43bdf762c36a","datavalue":{"value":{"entity-type":"item","numeric-id":4148937,"id":"Q4148937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$FB996869-C3A9-49C0-9C1A-0775B0449C19","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"46d6adff4ea3aa0f7d228b79121c4df04ec970cf","datavalue":{"value":{"entity-type":"item","numeric-id":436553,"id":"Q436553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$5DEA6799-0D18-47FC-98D2-3FD0B50D8C2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1f47c3d97015b3a26dbf1aa22eea5a634a9117a","datavalue":{"value":{"entity-type":"item","numeric-id":1931428,"id":"Q1931428"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$81951240-6D83-47BD-AE66-93EE95B29682","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1b8c9a82ade7e127eaa26c1b64b2c1ac969eb38a","datavalue":{"value":"10.3390/A6030485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1736579$2DAED4E1-E9DE-4ED8-ABC0-3C483555073E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c78b85270af96d02dd0498e598b536484d2f28a","datavalue":{"value":{"entity-type":"item","numeric-id":2445236,"id":"Q2445236"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac0a6e89d26ffe82db3e4097cfa865b3020da5b5","datavalue":{"value":{"amount":"+0.9417553544044496","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736579$BE14E795-7843-4439-B093-CCC7175BBF57","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"320af1db8a56620de6dee3a858682ab7543fecf7","datavalue":{"value":{"entity-type":"item","numeric-id":2447542,"id":"Q2447542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"272a109c7b19efdfa089c864038c8ef6522329cf","datavalue":{"value":{"amount":"+0.905672013759613","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736579$CA290A54-A6BF-45D2-AD7E-93C44786FFCD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bdb0beed4a978b2b51cfb9033564247296b9782d","datavalue":{"value":{"entity-type":"item","numeric-id":489728,"id":"Q489728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"19fc32e05681626cccfabb260b488b667dfc54ff","datavalue":{"value":{"amount":"+0.9031983017921448","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736579$A48CA380-C203-490A-8BC3-9A174D3E82DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80c6612ef50b496d4466ed9ef245bf21620e2448","datavalue":{"value":{"entity-type":"item","numeric-id":3297762,"id":"Q3297762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0342eaa4364581831bba9ff531bc3b409be2b36","datavalue":{"value":{"amount":"+0.8977765440940857","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736579$7694CBE9-1A0E-42BC-AD43-E79FB2774833","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b899d7930710476494e159631a6a08b80b7e3f90","datavalue":{"value":{"entity-type":"item","numeric-id":1029006,"id":"Q1029006"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3d62481cd0e07a1531ec9baa31bd9f475f6ff6f1","datavalue":{"value":{"amount":"+0.8593385815620422","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1736579$0697FAB9-5128-4CB4-87F7-E519EC2C53D2","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1736579$9C51DC4A-CE07-4045-BC55-A1E8E5F28DC8","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1736579","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1736579"}}}}}