{"entities":{"Q5097510":{"pageid":7127086,"ns":120,"title":"Item:Q5097510","lastrevid":54387101,"modified":"2026-01-26T18:02:31Z","type":"item","id":"Q5097510","labels":{"en":{"language":"en","value":"Approximating longest common subsequence in linear time: beating the \\(\\sqrt{n}\\) barrier"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7575638"}},"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":"Q5097510$CB49C90D-2547-4573-A2C9-645774487D4A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"dc3fc4b4beadafdc49f0649a17da23d1bbfbb765","datavalue":{"value":{"text":"Approximating Longest Common Subsequence in Linear Time: Beating the $\\sqrt{{n}}$ Barrier","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5097510$C9602ED3-1864-413F-9CC9-AD3890258052","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"367366f54112d8da6155291a2f6989e287caa026","datavalue":{"value":"10.1137/19M1272068","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5097510$82CA495F-4BBB-4837-9066-1FAEEDC3905E","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"9468428389e0a00c9c8e46fc301008aa1001c1fd","datavalue":{"value":{"entity-type":"item","numeric-id":1739116,"id":"Q1739116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$F104E443-50F9-44E3-9F51-2FCBA8900B9F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0ed5e1ff4e4821fadc396b24895cbf8ad96258d","datavalue":{"value":{"entity-type":"item","numeric-id":5097509,"id":"Q5097509"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$89E5C10D-EB90-4582-A09E-5B0017083712","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b1fafbfdbcba730df23f71f6b7ad97fc662ceddf","datavalue":{"value":{"entity-type":"item","numeric-id":726338,"id":"Q726338"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$18F3C996-A1E4-48EA-A267-721A452A11A3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3098471736f417aa552d69c3165075e7ba3a336f","datavalue":{"value":{"entity-type":"item","numeric-id":487271,"id":"Q487271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$18FAB18B-0257-4213-A15D-E969D417C831","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$2B285D45-9CFF-4139-BED2-84FD157E15C5","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"1671f4d77625f9c3fb2d471bd3f2c3e84e79d65e","datavalue":{"value":{"time":"+2022-08-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q5097510$4FA3B1AE-A4D6-41D0-A9C3-681A2934CABB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"62a49b155c9af634e6c3562b1547da1f7c08791a","datavalue":{"value":"68-XX","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5097510$BA22B936-E22D-4582-8162-E5DF3CD9A2EC","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b885298a937a0432b239a002552fc17b4a0567e3","datavalue":{"value":"7575638","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5097510$FE3A4DE0-BEF7-457E-9AF7-B90CCDA1E8CF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"dc058f54aac0023b7543c366366b86bc4e72c56b","datavalue":{"value":"approximation","type":"string"},"datatype":"string"},"type":"statement","id":"Q5097510$1AFC5B6C-B1E6-4369-A142-433DDA90BA9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3f0a0bf79411772273f5086c3d5a2f297706f321","datavalue":{"value":"longest common subsequence","type":"string"},"datatype":"string"},"type":"statement","id":"Q5097510$506C93F5-D692-495F-8A21-BA78BC643CF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"da6c78b67096b558b6a5b7f77cad8eea1fc65662","datavalue":{"value":"linear time","type":"string"},"datatype":"string"},"type":"statement","id":"Q5097510$F4F8A474-2E6E-4CA5-8224-D7CED81E1B22","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":"Q5097510$CC3E5314-B299-4BDA-85DB-4A581C65AA1F","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"ad09bcd093d947d2c04ea48f1ec4a9919b87a5dc","datavalue":{"value":{"entity-type":"item","numeric-id":4638059,"id":"Q4638059"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$A3277F73-D9B0-4092-A6FA-76DF8F0AB6EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f64c9aadb37abd6e7fbf7ca22480998297c44e73","datavalue":{"value":{"entity-type":"item","numeric-id":4993300,"id":"Q4993300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$1FFB1B94-13A3-452F-BF88-5556A43F8DA5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"73c7cec10f75f37a3d3ec5336df6610144935b32","datavalue":{"value":{"entity-type":"item","numeric-id":4933374,"id":"Q4933374"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$FFB32625-ECFF-4408-8F5F-FC69715C2906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b2840b356506435518d4c57b03598b0d3706b52","datavalue":{"value":{"entity-type":"item","numeric-id":5172713,"id":"Q5172713"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$9BDB7EAD-8A77-481A-87C1-66C4CB5D0BAD","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":"Q5097510$43E10358-3C09-4495-BD14-36B7295DFA87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"038612069e78e54967945014fe68cd284f9a85f0","datavalue":{"value":{"entity-type":"item","numeric-id":5714657,"id":"Q5714657"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$1C56717A-0EDA-4D73-94E0-104FE7ACAF35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b52fa7fd27124acec7f37226ed3641e8ce081efe","datavalue":{"value":{"entity-type":"item","numeric-id":2941488,"id":"Q2941488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$8E29C0C5-7872-47AA-98DE-9C93EA0D2FEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27329418648ed5811311868e6639c7ec3f856bdc","datavalue":{"value":{"entity-type":"item","numeric-id":3581511,"id":"Q3581511"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$A869D672-BF29-40F1-85CA-7624AEEB5654","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a860092cae4ad4c5ee631c0a98f0a7ee7f9c9d0","datavalue":{"value":{"entity-type":"item","numeric-id":3241581,"id":"Q3241581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$C616A8D7-B379-4A3A-9006-0DB7DBF114CA","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":"Q5097510$86D5EB2C-1D61-45D5-AD81-44681B4FE101","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3562d5c96e3f49fa9c028395569cceea974a8e92","datavalue":{"value":{"entity-type":"item","numeric-id":4607964,"id":"Q4607964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$BB67D5A2-EAD9-41DC-BAF1-CDF2A369CB31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2f69fb2a291374be4f92a5a2903921987dbd9bd","datavalue":{"value":{"entity-type":"item","numeric-id":5146877,"id":"Q5146877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$D1F1103D-78A8-46AC-B8B6-DEC4DCEF9357","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"007c64cb1e51e420a82b1528582743678952b922","datavalue":{"value":{"entity-type":"item","numeric-id":2648578,"id":"Q2648578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$85B97C96-046A-4A9A-AC1C-A2C3AD927FB0","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":"Q5097510$ED58A3CB-5899-4CA7-8346-42B0099648E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"767f9f1665adb38a99b5a9ed823fb521da3021ef","datavalue":{"value":{"entity-type":"item","numeric-id":5236284,"id":"Q5236284"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$C0FC5664-1D25-4E36-A5D9-16FAA88790C2","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":"Q5097510$EBDB11C0-C827-4FEA-9A5F-35A29FEBDED1","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":"Q5097510$88212925-0A13-4F25-A224-E95D9E7262CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d04b8dea9fe41d21fcb8d7ea3b348b53e25cbab5","datavalue":{"value":{"entity-type":"item","numeric-id":786541,"id":"Q786541"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$68691D2A-1876-4F42-80DB-B862DEC24CE7","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":"Q5097510$31BCABA4-B769-4996-A553-783E31569F75","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7b7c8a305876ea257ba1e38c2d0cf95e4a25bf4","datavalue":{"value":{"entity-type":"item","numeric-id":2723948,"id":"Q2723948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$E22441ED-163A-419A-80F8-33F78D66CA31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b29c6873abbc02300c1cb0f658b3c10af08da0d8","datavalue":{"value":{"entity-type":"item","numeric-id":4388886,"id":"Q4388886"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$598AA628-3CB6-4ADA-AD41-86AEF5C401F0","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":"Q5097510$D20BB248-8799-4882-8E62-21A212EA7CD4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4333811af5dc7ed5617cb6da83be69dde7fe1560","datavalue":{"value":{"entity-type":"item","numeric-id":5678900,"id":"Q5678900"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$1F3ED8B0-D428-4C42-AA1A-0B1E05DFC745","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":"Q5097510$D51E807B-3C64-4E11-BD76-DB817575146C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a1df1121fb0b7e22980fdc0da265cda61dc7c47a","datavalue":{"value":{"entity-type":"item","numeric-id":5096874,"id":"Q5096874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$32ABE3A9-F03C-450A-9B13-2990D1825614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8fe979badcb8bfb7a41b5de5f764eb66747617dd","datavalue":{"value":{"entity-type":"item","numeric-id":5781249,"id":"Q5781249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5097510$11B686B2-35FF-48AD-8178-3300C4056BB2","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":"Q5097510$5AA1F29D-2024-408D-BD75-58073FD01305","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"fe73428a3ad9719de90ac61e21bfd2bbbec98775","datavalue":{"value":"https://doi.org/10.1137/19m1272068","type":"string"},"datatype":"url"},"type":"statement","id":"Q5097510$1DA5A4BB-3534-426C-BE18-07A531FCBF36","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0824daa413055ace508dd528db8904072e377935","datavalue":{"value":"W4293037332","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5097510$2C76E2EB-01A3-4036-9C34-437ED1083C0A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"09b3502f3e5ab6e2a99f1f9e337aad06bd740aff","datavalue":{"value":{"entity-type":"item","numeric-id":5236256,"id":"Q5236256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bacb65250003a960604ae8bc60965b7ae591de2b","datavalue":{"value":{"amount":"+0.9933345913887024","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":"Q5097510$E0402165-A4EC-45C4-8483-BDE8D54DE13A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ff875296fb7d15e7bc45612891dcdda437178b5e","datavalue":{"value":{"entity-type":"item","numeric-id":3060772,"id":"Q3060772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b2f5b672809514fd6fa87c11f2b55823c32455d7","datavalue":{"value":{"amount":"+0.8292021155357361","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":"Q5097510$1C075E5D-A606-42BA-A73D-0FFDBEEE4962","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3cc94786ace4a65eccf3f739ded874bb3a46b2d2","datavalue":{"value":{"entity-type":"item","numeric-id":439929,"id":"Q439929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0155cab8cf75e97041425a311f33bab6c2bc8004","datavalue":{"value":{"amount":"+0.8288376927375793","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":"Q5097510$2FB8BCE1-4CA1-4BF4-9751-FB93FC992D6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"64d11b739abf30c82edd7497ae70ba0228ada87b","datavalue":{"value":{"entity-type":"item","numeric-id":3506958,"id":"Q3506958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27d6701a6f7b7f4762692bc3624637027bc92bd5","datavalue":{"value":{"amount":"+0.8101894855499268","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":"Q5097510$39028592-E789-4EAA-82F0-5EBA860E52D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"542d971078d9eb02e7c886ee3a8bb40042d8ebe4","datavalue":{"value":{"entity-type":"item","numeric-id":716327,"id":"Q716327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9cca2949ad926242a8191a6530629be3b6704058","datavalue":{"value":{"amount":"+0.8098371028900146","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":"Q5097510$C456F64A-1426-4A2A-9112-DA865248AB2D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5097510","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5097510"}}}}}