{"entities":{"Q1098310":{"pageid":1109062,"ns":120,"title":"Item:Q1098310","lastrevid":49138054,"modified":"2026-01-06T15:57:02Z","type":"item","id":"Q1098310","labels":{"en":{"language":"en","value":"The longest common subsequence problem revisited"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4037236"}},"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":"Q1098310$96AD8F98-438E-47C9-82DA-33D9790D31EC","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41a3ea8c3628a7cc60f03cb819e9f369a11f1108","datavalue":{"value":{"text":"The longest common subsequence problem revisited","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1098310$7C45BA73-DB67-4EDF-9F1D-EBA701A60F33","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"31f8b232f946edd1faa7cc412dfc122facb824b0","datavalue":{"value":"0636.68083","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098310$53E1C824-F631-4E3B-9FF9-891FFD0DCE61","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"38afe6e7bfaa86c2cd6c7d361b510b08a6dafc89","datavalue":{"value":"10.1007/BF01840365","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098310$E134F195-B3A3-42D8-91F1-B3DC51625E82","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"65c8fa095fb5e7de7a6818fd747ab8b39647de93","datavalue":{"value":{"entity-type":"item","numeric-id":96582,"id":"Q96582"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$B69BD153-7390-4564-8212-BC2A533EB8F8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5ae48c61eed19d1e1e1f33f9255d5b329362d064","datavalue":{"value":{"time":"+1987-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1098310$22253D77-8EF7-452D-A20E-E046D20337F0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"75f33c298bdb611b98c5735211b1d913a8a0878a","datavalue":{"value":"This paper re-examines, in a unified framework, two classic approaches to the problem of finding a longest common subsequence (LCS) of two strings, and proposes faster implementations for both. Let \\(\\ell\\) be the length of an LCS between two strings of length m and \\(n\\geq m\\), respectively, and let s be the alphabet size. The first revised strategy follows the paradigm of a previous \\(O(\\ell n)\\) time algorithm by Hirschberg. The new version can be implemented in time \\(O(\\ell m\\cdot \\min \\{\\log s, \\log m, \\log(2n/m)\\})\\), which is profitable when the input strings differ considerably in size (a looser bound for both versions is \\(O(mn)\\)).    The second strategy improves on the Hunt-Szymanski algorithm. This latter takes time \\(O((r+n)\\log n)\\), where \\(r\\leq mn\\) is the total number of matches between the two input strings. Such a performance is quite good \\((O(n \\log n))\\) when \\(r\\sim n\\), but it degrades to \\(\\Theta(mn \\log n)\\) in the worst case. On the other hand the variation presented here is never worse than linear-time in the product mn. The exact time bound derived for this second algorithm is \\(O(m \\log n+d \\log (2mn/d))\\), where \\(d\\leq r\\) is the number of dominant matches (elsewhere referred to as minimal candidates) between the two strings. Both algorithms require an \\(O(n \\log s)\\) preprocessing that is nearly standard for the LCS problem, and they make use of simple and handy auxiliary data structures.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098310$FCBDA250-B118-4AA6-A525-6BBC0F411ED2","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"3f97694d44af155a68434cb72eabc6a4d5dd5227","datavalue":{"value":"68P10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098310$80502096-BA2B-47E1-BD46-5A6C0DC88514","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098310$E1B473BC-C234-4C49-AF0E-61773979DDB6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"16199bb4de9bc9d057265f846b322d502c19ce46","datavalue":{"value":"4037236","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1098310$3601731F-163F-4CFA-9078-ADDF7EA4582A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7442c46a87c4b4834bcc381d5ad2b3dda8b08849","datavalue":{"value":"efficient merging of linear lists","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098310$6B5566ED-03A1-49D1-A90D-233F083D2EC7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f0a0bf79411772273f5086c3d5a2f297706f321","datavalue":{"value":"longest common subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q1098310$2D734175-0D49-4826-A5E2-0CE9629EEA16","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"873796445b5ce8d61b5ea73cdea0956f7aecf751","datavalue":{"value":{"entity-type":"item","numeric-id":294937,"id":"Q294937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$72DADE30-9A77-4F92-B677-EA55EE39EBF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"1e1e555bd8f1835181bb8ca17454287967a4f277","datavalue":{"value":{"entity-type":"item","numeric-id":294938,"id":"Q294938"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$C59B535E-15E1-408F-84A9-482827E0663E","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":"Q1098310$018E4216-A83F-4466-95D3-7BBF06F7CDE4","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"449a3a8bbd1b47a2cffea1176dbbe7559748f4c1","datavalue":{"value":{"entity-type":"item","numeric-id":4077445,"id":"Q4077445"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$358D2ED0-3DAA-4C5C-8C75-8D680259D0E4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"db21cffc9a30e21b6f7d43dc8fec24dc554ce3ce","datavalue":{"value":{"entity-type":"item","numeric-id":1085982,"id":"Q1085982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$2FFF5AA5-4F2C-47BC-B479-C32DAE9E25EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddd7cf5c3cf20a3faedc8fb513c29ca711e97cb6","datavalue":{"value":{"entity-type":"item","numeric-id":1229581,"id":"Q1229581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$F3AA72DB-60DD-41F6-8BB9-6DEA979FF8C0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68a4e203eb7c84092fa290a427adcc4cfb08285e","datavalue":{"value":{"entity-type":"item","numeric-id":5402537,"id":"Q5402537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$6B4A809B-0E32-4248-9D10-F0C5C749E61B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fc296f5e5e1f68e997d322609535949ec48417cc","datavalue":{"value":{"entity-type":"item","numeric-id":4178502,"id":"Q4178502"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$464F50F7-D7AF-4B8A-9B48-FC21A911E6C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"696366a94654a5d30f96d57b0e6b7e9de909ff30","datavalue":{"value":{"entity-type":"item","numeric-id":4055176,"id":"Q4055176"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$4478F264-4241-4DF4-B55C-0BA0262DD5C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"479f4dcfe2a2bf628395ba07248e3327e13c5b44","datavalue":{"value":{"entity-type":"item","numeric-id":4187318,"id":"Q4187318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$0FA388AB-96FA-488C-9C97-CC1AD16CE4DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55053ba8d02f87c1d3b60fa956f8365744470121","datavalue":{"value":{"entity-type":"item","numeric-id":1072704,"id":"Q1072704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$CED8A039-8247-4CBE-BF98-1619D4F67C79","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4861b889694d4cd2c5f38eb801b0fa0c2924ad9","datavalue":{"value":{"entity-type":"item","numeric-id":4125781,"id":"Q4125781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$DEE49C1B-A8BA-46EC-86CF-A8EA701E7757","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dc28553cbd079f414114c265d86a94b6ad484595","datavalue":{"value":{"entity-type":"item","numeric-id":1140994,"id":"Q1140994"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$20F55102-0B52-4116-8147-5E03408245F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9387bbd38b0874a230355988a020913f3259fce1","datavalue":{"value":{"entity-type":"item","numeric-id":3219751,"id":"Q3219751"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$953C132E-A41A-4993-8F6F-EE39CD50F45A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0ba2a12b9e1e5e9bec0aede63e4f328974ff5dc6","datavalue":{"value":{"entity-type":"item","numeric-id":1241058,"id":"Q1241058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$D93D560E-A0F8-4A1A-A8FC-9B435718EBEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e6f12679e730f186e807cbb39398fa0f8075753","datavalue":{"value":{"entity-type":"item","numeric-id":4404425,"id":"Q4404425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1098310$56B2142A-513B-4AFB-8450-062AC244EDF2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80c76d82ad850dec0f1590d456ac4854ab4dec3c","datavalue":{"value":{"entity-type":"item","numeric-id":1085982,"id":"Q1085982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74e1355bfd988f93458eb78b0c18e8d08c049c11","datavalue":{"value":{"amount":"+0.9169193506240844","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":"Q1098310$FEB76B67-3AE5-4874-BCA1-DD41E7411E8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7f04a95af8471ef46a86274f1dda45f40d4d6f84","datavalue":{"value":{"entity-type":"item","numeric-id":4432974,"id":"Q4432974"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"af13b1de59b3532b27ad499785077104d55174ae","datavalue":{"value":{"amount":"+0.9030752778053284","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":"Q1098310$AB10E150-20E6-4336-A757-F535ED182203","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d3e1a1894df350fc78071e7cc183433fc4fd2f8","datavalue":{"value":{"entity-type":"item","numeric-id":1072704,"id":"Q1072704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f429a54cf663f2002988fa4d133a77b78331bcf6","datavalue":{"value":{"amount":"+0.9023101925849916","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":"Q1098310$F15A59C1-A757-4BB9-B7B1-2919AEE1E05B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d9160a951819b0ba1736802064a682ed12583afb","datavalue":{"value":{"entity-type":"item","numeric-id":4862293,"id":"Q4862293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e101577540321374631e7b1b9ff86f95770b079f","datavalue":{"value":{"amount":"+0.8878021836280823","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":"Q1098310$2CF534F8-EB85-47CE-BA81-A5BF518F673C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"100f1c070bc0362482fa0e144129d9ec01cbea61","datavalue":{"value":{"entity-type":"item","numeric-id":1190449,"id":"Q1190449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e377f98c98fd20c4e398ef1e61c765427376186f","datavalue":{"value":{"amount":"+0.878975510597229","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":"Q1098310$4C489751-8B17-4DB6-89FA-7E3E6E761E93","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1098310","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1098310"}}}}}