{"entities":{"Q1720875":{"pageid":1731616,"ns":120,"title":"Item:Q1720875","lastrevid":69024387,"modified":"2026-04-13T03:48:19Z","type":"item","id":"Q1720875","labels":{"en":{"language":"en","value":"An efficient algorithm for LCS problem between two arbitrary sequences"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7018926"}},"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":"Q1720875$1DFCCEF9-9E36-4D8C-985D-A6AC235C9B6D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"413b7c71b8603eea51056700997d9cfd2e73950b","datavalue":{"value":{"text":"An efficient algorithm for LCS problem between two arbitrary sequences","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1720875$DA66B4D2-F113-4B34-B3A5-F8F5A7077AFF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"df0b75d0558d0f12e5ceefc8d2b9326c6061300e","datavalue":{"value":"1427.68375","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720875$7506F710-0A1C-44B6-8855-A82FEBF772DA","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0f81783b246ed31d4923e59f0d09691084c0d83d","datavalue":{"value":"10.1155/2018/4158071","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720875$088E3015-4FD2-4067-825A-C1B501C2AB29","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"24f652ce04a200a2e9302589f3f53da9c2a35b29","datavalue":{"value":{"entity-type":"item","numeric-id":893778,"id":"Q893778"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$ACFA402E-2E05-486E-A8C7-BF6FA27DDA0E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3dc97bc0aff607b9c22ce37ffa18b6de85001d90","datavalue":{"value":{"entity-type":"item","numeric-id":86199,"id":"Q86199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$308576A5-8AE9-4646-942A-FC2C62936083","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"32a6dc046c0aa99508538df457dbadf7aa620337","datavalue":{"value":{"time":"+2019-02-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1720875$60C9F58C-CF83-444D-A06E-8924F3EF20C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8aad86f72c6767ef8b38b29c14cb4208fb3e98da","datavalue":{"value":"Summary: The longest common subsequence (LCS) problem is a classic computer science problem. For the essential problem of computing LCS between two arbitrary sequences \\(s 1\\) and \\(s 2\\), this paper proposes an algorithm taking \\(O(n + r)\\) space and \\(O(r + n^2)\\) time, where \\(r\\) is the total number of elements in the set \\(\\left\\{(i, j) \\mid s 1 [i] = s 2 [j]\\right\\}\\). The algorithm can be more efficient than relevant classical algorithms in specific ranges of \\(r\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1720875$25B13410-CFA6-4486-8A97-BEDB3FA29B0D","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720875$B9BBC96A-F19D-4683-A7CA-22028D6DDBA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7ddaa80bf0a693a36c1113ff6b7ad576f729940","datavalue":{"value":"68W40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720875$DB44959C-808C-4BB2-A4E3-9B0C6C191921","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"24b3253d0eabae0a3cd0615d6f58b1c019909937","datavalue":{"value":"7018926","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720875$490E3CF5-F3AA-4934-9F3A-8E5B203ACE04","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":"Q1720875$63446013-E979-45A7-9CA0-43E8FDC57AA3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"410fd3ad16325f75505aef3fe790965774f9519b","datavalue":{"value":"https://doi.org/10.1155/2018/4158071","type":"string"},"datatype":"url"},"type":"statement","id":"Q1720875$6663C788-ABB7-4CA5-AA30-92F0A29ED341","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4b0b6d1d8cc0a750f207b324364267a7148a1bac","datavalue":{"value":"W2903386140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1720875$A9BC91D0-D87A-4BFF-B43B-0538635C7DA6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"659cdaa15ad6d89ec32129a4bed8372f5f89fdf6","datavalue":{"value":{"entity-type":"item","numeric-id":4147591,"id":"Q4147591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$26491E7C-8BE6-46C4-8BFB-B32C8807B5BF","rank":"normal"},{"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":"Q1720875$BE29E6C0-7021-461A-B532-212F8817817C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27a38a0c3b8313d461c9336737cfa7f6dbb28b7b","datavalue":{"value":{"entity-type":"item","numeric-id":4072574,"id":"Q4072574"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$E9939A6A-3755-4FE0-98B8-0D8C36103A15","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":"Q1720875$E1087673-D4FE-4A1E-83A3-A64B0DD2A239","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":"Q1720875$831A2E0F-FEB8-45FF-9823-B926EFF91371","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"502ec834779d490b3452a9d3c12cd58b539ff10c","datavalue":{"value":{"entity-type":"item","numeric-id":1168731,"id":"Q1168731"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$994F845F-02C4-4DC1-ADDC-5DD441A9E6F8","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":"Q1720875$661A87A8-A9C7-48D8-86DF-611416C5F162","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27c6e757fd939cfe5ef7651bac1e14aaf8f9e188","datavalue":{"value":{"entity-type":"item","numeric-id":1098310,"id":"Q1098310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$F00A1D7D-0871-4F06-9699-45FAC9E447E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a89cb60ae823985ce14098bf94eb89dfbead6e64","datavalue":{"value":{"entity-type":"item","numeric-id":4302802,"id":"Q4302802"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$9A694042-807D-44A8-AC17-2051D3E7316D","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":"Q1720875$D7337E48-BFFA-4EEC-A9C0-CB27E1A41160","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c164f040680170f3ed5985371f5714b4c12ab924","datavalue":{"value":{"entity-type":"item","numeric-id":5616735,"id":"Q5616735"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$1BA43E46-9379-44EF-9834-143060256075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b0f454f3281122c373d744b02f4808cc572d85","datavalue":{"value":{"entity-type":"item","numeric-id":2378530,"id":"Q2378530"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$CCA01162-793C-4DBE-8DFD-01A1299D4224","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cee04d2f5ee034da895cfa41c0fde0a26fd47a34","datavalue":{"value":{"entity-type":"item","numeric-id":313774,"id":"Q313774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$3BC86811-FBA5-4275-8ED9-767632CC4007","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33a25cb0a4a1f58a54d68dd3a87c3010bcbd02e9","datavalue":{"value":{"entity-type":"item","numeric-id":1996891,"id":"Q1996891"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$1D0B5A96-68BE-438D-9F24-624BB6EF7298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"226e5f5d0bf05c40313ee9c8298aa7949d5d77ac","datavalue":{"value":{"entity-type":"item","numeric-id":1607132,"id":"Q1607132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$0E96FEAE-2592-478C-BB67-BC662CC6291C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"138d808c1a0d7bbfa300ea1020e86219b9fb4bf4","datavalue":{"value":{"entity-type":"item","numeric-id":4229812,"id":"Q4229812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$D303A426-A6B7-4DBA-BF5E-151032E05639","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eae80461e6efbcfc0a11d7c73ba89d94023d769e","datavalue":{"value":{"entity-type":"item","numeric-id":1205970,"id":"Q1205970"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$1B5FD380-08C4-4D14-A5F3-DC2BF29342A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a5b6949a2177b8076f2f374d95357da2b1d95b62","datavalue":{"value":{"entity-type":"item","numeric-id":1595937,"id":"Q1595937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1720875$36CFC6DC-AAC8-4E69-9C5F-651029857A8E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"656ed9ba57447972f246a0d0ea529652901a7db4","datavalue":{"value":{"entity-type":"item","numeric-id":733720,"id":"Q733720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a943a1b5998a70aac57906e5cf5e683976cf6d99","datavalue":{"value":{"amount":"+0.8817663788795471","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":"Q1720875$5E04C898-E3F6-4071-A5E0-98D16AEFCD2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f13d0036779f6663be417781c04c62f6fe93cc15","datavalue":{"value":{"entity-type":"item","numeric-id":5434425,"id":"Q5434425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a3cf62cd78a1d10165faa2368dea32c0914f4ac1","datavalue":{"value":{"amount":"+0.8573328256607056","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":"Q1720875$7308987F-5F1D-489D-A22F-7EEB060FB07C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"54a9cb423bcdfc5a4252be82bba2db6b98ca8c71","datavalue":{"value":{"entity-type":"item","numeric-id":3143773,"id":"Q3143773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2315560ef785e66ff4e7e60872594719bae02e6c","datavalue":{"value":{"amount":"+0.8213961124420166","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":"Q1720875$27689713-849B-47C0-9FB0-54726FAA7F2F","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":"846f73cbb99407d24127d42964e79239758281f3","datavalue":{"value":{"amount":"+0.8203700184822083","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":"Q1720875$2945E66F-358D-4CE1-8AE3-5805346A79A8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a3f744223b940492b54ad1277e8a052d6a3a09d8","datavalue":{"value":{"entity-type":"item","numeric-id":1101217,"id":"Q1101217"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8ec06942a017ad61ff4f0a9def6f1ade863cf959","datavalue":{"value":{"amount":"+0.8195119500160217","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":"Q1720875$9EB69834-4D4F-47CC-ABF3-2AD62DE02025","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":"Q1720875$85056436-F77C-4893-8B23-0B52F360108F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"An efficient algorithm for LCS problem between two arbitrary sequences","badges":[]}}}}}