{"entities":{"Q685487":{"pageid":687336,"ns":120,"title":"Item:Q685487","lastrevid":42641203,"modified":"2025-07-07T14:52:55Z","type":"item","id":"Q685487","labels":{"en":{"language":"en","value":"Tight comparison bounds for the string prefix-matching problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417398"}},"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":"Q685487$1B2BF5DD-0385-49AE-BE4A-27DD02AFEEC0","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1e203c037b7c818adafe64644b28f76b0c2277ea","datavalue":{"value":{"text":"Tight comparison bounds for the string prefix-matching problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685487$DAA6ED67-6C21-4A99-B68A-908F6696031D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07082b1c751aa30fc406b2742f4d3c7f68c7343f","datavalue":{"value":"0802.68066","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685487$996A1C8C-42BC-4182-8743-C420272CC3E0","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c1704b1360d6d079ddb4a65b86f1c34869ea28e5","datavalue":{"value":"10.1016/0020-0190(93)90156-4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685487$B2F1418F-688F-4CDD-9671-7D5F3D16E3E3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c57e34fb306da46440f3216d029392a7c5291ca8","datavalue":{"value":{"entity-type":"item","numeric-id":287047,"id":"Q287047"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$E16D7DB9-F37C-4021-A368-5186995B9031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"972dafc21227477a61fcc40f2e7e53fc5c847496","datavalue":{"value":{"entity-type":"item","numeric-id":671353,"id":"Q671353"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$944CCDC9-0F4B-4FFB-8094-3F42905C2F9E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b7013a19b9393ba53308b594c966532ac5a6b722","datavalue":{"value":{"entity-type":"item","numeric-id":671354,"id":"Q671354"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$BF2C53F5-208A-435C-BEA2-E1700F38E64E","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$F4719201-25A6-432B-B0D8-3F57F84E4DE2","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"10b8be3aaae04a8b6e1fb062263f34380fce1ca5","datavalue":{"value":{"time":"+1994-12-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685487$D4F96043-579B-425C-B396-6B767D319F0E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5b1ceb92435f86d695e83d77c4939f53ca95d768","datavalue":{"value":"https://ir.cwi.nl/pub/1524","type":"string"},"datatype":"url"},"type":"statement","id":"Q685487$2299BE49-2827-4308-A885-0D5014E365B8","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c20e4af123349375dd61e11d6b03bf642aaae1a","datavalue":{"value":"The authors study the following generalization of the standard string matching problem, called string prefix-matching problem.   Given a text string T\\([1\\dots n]\\) and a pattern string P\\([1\\dots n]\\), compute an integer array \\(\\pi [1\\dots n]\\) such that for each \\(i\\) \\((1 \\leq i \\leq n)\\), \\(\\pi [i] \\leq m\\) and \\(\\pi [i]\\) is the largest integer satisfying T\\([i..i + \\pi [i] - 1]=\\text{P}[1..\\pi [i]]\\). I. e., \\(\\pi[i]\\) gives the longest prefix of the pattern P that coincides with a substring of the text T starting in position \\(i\\).   In this paper the authors give upper and lower bounds for the exact complexity of the string prefix-matching in the deterministic sequential comparison model.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685487$22C33957-3AF9-47B1-8C18-7A21F3FBE5F4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"cb3a3ba65440da04d49f30062ed2e12f784ddb41","datavalue":{"value":{"entity-type":"item","numeric-id":235683,"id":"Q235683"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$73212A76-8DF9-4CA7-BEB6-67BEE4D2BD43","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685487$E4614C15-95DA-422C-8D1D-CB455C65AE7F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685487$ECBB666D-8933-46F5-B3DF-B406E23127B6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"aceb246725ee7236ff7d493319858e465f993e9d","datavalue":{"value":"417398","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685487$E4B63806-88A2-4B19-963A-381C8019C9E8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a3ec71f0b5f4d8c01da75d533235393f1af170e2","datavalue":{"value":"prefix matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q685487$6D80A440-BA66-4BA3-BBF4-A2B180E0A17C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2f3a4134a14189694b76416ccebed15be1ca2af8","datavalue":{"value":"patterns","type":"string"},"datatype":"string"},"type":"statement","id":"Q685487$890F85B8-1E06-4046-9F68-4582CF13545A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d14f17015cc2709565c880285793cb81bdfd1835","datavalue":{"value":"string matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q685487$B59E31A1-CC0C-496B-95B4-410BC2B98D07","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":"Q685487$2798B84D-0BF5-4D4A-9612-436068DF25DD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"b7a61ff6d386d2e36cdeb9c8c10ea29b4edb3074","datavalue":{"value":"W2048532915","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685487$F6E0CCEA-E1CC-41B2-984C-9F90262EA0D9","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"dd3a7cfeece8562a9ac87120b107e2b528967937","datavalue":{"value":{"entity-type":"item","numeric-id":4773298,"id":"Q4773298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$32C8BF4D-A479-4817-963F-65A406FAE3B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74e200c4f897ac4cb0c5ae9f1bab6477c1d7e3dc","datavalue":{"value":{"entity-type":"item","numeric-id":3090391,"id":"Q3090391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$B21F7355-9FEE-45AA-8625-E57EEB4DEF86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2186eafcf60881276ded9ffd592403c0a752a3c0","datavalue":{"value":{"entity-type":"item","numeric-id":1311385,"id":"Q1311385"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$72609D17-162D-4BE3-B3D5-4940FACAAF90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4990204a8dcd76e601aff36b664f195be6e13da","datavalue":{"value":{"entity-type":"item","numeric-id":4228434,"id":"Q4228434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$D780A4F9-E060-4785-B1FC-0CC1006260B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ee7c875492fb9a44fb5b6ff2fe6c24db3844b31f","datavalue":{"value":{"entity-type":"item","numeric-id":1183611,"id":"Q1183611"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$F5F99E8D-739B-4BCA-9F9E-A83788C86715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6adb7e7aa715447704bcfc1f51f1cfc1f38fe1f5","datavalue":{"value":{"entity-type":"item","numeric-id":3985805,"id":"Q3985805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$00054D0E-767F-4242-87E7-4B7D738CCDB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"de78d69e7691abce7302f62b30a5ccdd26b8ae1f","datavalue":{"value":{"entity-type":"item","numeric-id":4016906,"id":"Q4016906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$7F6FF0B6-EBBE-4EA9-8ECB-FBDDE2057BD0","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":"Q685487$B0616713-11F6-490D-8D86-5AC9CA2F1CB5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8e3b7ca5b3940eabd88b0adad7b747976d441fd0","datavalue":{"value":{"entity-type":"item","numeric-id":4142690,"id":"Q4142690"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685487$CA159303-0AA5-41CB-884F-D029DA61A10D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3fc0cb4402d4173888626bbc3f900f94b0da9bd","datavalue":{"value":{"entity-type":"item","numeric-id":4217300,"id":"Q4217300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13fd8814dcdbc868111134b8403e8b7c967d596a","datavalue":{"value":{"amount":"+0.9650414","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$73AF05D3-DB25-4FE6-8A48-191D2D87C77B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bd1a16c43e4aea5b7a7745bb47696335ea95b8d3","datavalue":{"value":{"entity-type":"item","numeric-id":5463440,"id":"Q5463440"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8816da747e64753146ab72761bcbf6869e7c9371","datavalue":{"value":{"amount":"+0.93076926","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$BAB7B39C-ACAC-41E5-B35C-955B5CC1F4E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91a41813b82247e3f273e65dbe0f9a594197e23b","datavalue":{"value":{"entity-type":"item","numeric-id":4340774,"id":"Q4340774"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9b280b2cd41359f81d38da6805249f22dd4c94e8","datavalue":{"value":{"amount":"+0.9192654","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$E75C261B-9EDE-40E1-9CED-B98737DA5CCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"316bfbe8ea796de798b982f8a320341286d6d259","datavalue":{"value":{"entity-type":"item","numeric-id":4326851,"id":"Q4326851"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a9b21fc7c41e36be809810b5930b3dbdb7c3b624","datavalue":{"value":{"amount":"+0.9190759","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$BFFEF43C-82B7-426B-A62B-AB413F2E9948","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"71770eaeee2d970df485fb9d661aa7c12b3c1ffd","datavalue":{"value":{"entity-type":"item","numeric-id":4228434,"id":"Q4228434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80d310cd2dfb6d52a2215ede636f03e5e362fb84","datavalue":{"value":{"amount":"+0.913441","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$5B5DBF72-5DB5-4E13-88E3-46EB1B52F33A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d7bfdd6e5c72576934216b2d143f32ac505a470e","datavalue":{"value":{"entity-type":"item","numeric-id":4016906,"id":"Q4016906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"78d08697ff69c2bb7cf6ae7049501ef4eeb8cde5","datavalue":{"value":{"amount":"+0.90109086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$8A0D75E1-B752-487E-9903-71507CF860B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45612dd2832c13911992cf9a79aea473677bdaa9","datavalue":{"value":{"entity-type":"item","numeric-id":3985805,"id":"Q3985805"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5f489de8ce31baa9c40ad34850496965b33b9d7b","datavalue":{"value":{"amount":"+0.89715785","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$F8658F33-8A61-424F-92AA-A5B23FA80D59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ca5495bf3a28419b9b19968e1362419f7312bf59","datavalue":{"value":{"entity-type":"item","numeric-id":1326953,"id":"Q1326953"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"446b5d1e27aadc376dc723beec7edaecf06c54cb","datavalue":{"value":{"amount":"+0.89534974","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$AF15F7D6-957D-49B1-A61E-939AF36284E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5e643ffad6dd5bc2d1a8b8aeba45e9c4f5142142","datavalue":{"value":{"entity-type":"item","numeric-id":1108789,"id":"Q1108789"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f65c2120ae08b3644594d4bb6f9b7cc0eaecf5","datavalue":{"value":{"amount":"+0.88360274","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$5DBDD59A-AE5B-4BD2-AC0D-D56A6A6F29AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72fa9827c6678df4e3eb6949fc6adc5bbd401bbc","datavalue":{"value":{"entity-type":"item","numeric-id":4844575,"id":"Q4844575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cd8038993be94075237d600bef9b85475e8dc806","datavalue":{"value":{"amount":"+0.8758599","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q685487$C23BF8E0-FB35-40D0-8D3B-D51063821BBD","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:685487","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:685487"}}}}}