{"entities":{"Q40965":{"pageid":41021,"ns":120,"title":"Item:Q40965","lastrevid":105427685,"modified":"2026-10-09T10:08:07Z","type":"item","id":"Q40965","labels":{"en":{"language":"en","value":"Knuth Morris Pratt"}},"descriptions":{"en":{"language":"en","value":"AFP entry Knuth_Morris_Pratt"}},"aliases":{},"claims":{"P13":[{"mainsnak":{"snaktype":"value","property":"P13","hash":"82609789d0c55c035409ab8e174f0b2ee8f421c7","datavalue":{"value":"29251","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40965$117C3B0F-AA29-4F72-8202-D0235250015F","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"908c3454b3659c4b140ccce33c5aee31081edc8d","datavalue":{"value":{"entity-type":"item","numeric-id":5976450,"id":"Q5976450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$BC73FDC1-6C7B-4B80-A5FC-33065F7A42DC","rank":"normal"}],"P29":[{"mainsnak":{"snaktype":"value","property":"P29","hash":"41985f4a0fb23abcd45989ece8f698a9db9ff1d3","datavalue":{"value":"https://www.isa-afp.org/entries/Knuth_Morris_Pratt.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40965$18AC83A5-3520-4EE7-9718-5B06A2E05F56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"acf10290b955a69659a681d98822944f91bbad9e","datavalue":{"value":"68","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q40965$4B9877CA-AE54-4A82-BC68-7F9DEE1AB56C","rank":"normal"}],"P1458":[{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bb05cb23794774f62a8e4aa4de610af231973a1d","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$07F82B45-B545-48FD-9D28-BFDC2F3B7CB0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"a2a767ccd0e9bdc5b1b4a2069a6679f9340a857a","datavalue":{"value":{"entity-type":"item","numeric-id":14275,"id":"Q14275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$5D5FACE2-A5B4-4D6C-BC9F-B26E50349682","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"13de30f88d0d4fe9c5e21ee6f7da73ef297225d7","datavalue":{"value":{"entity-type":"item","numeric-id":30361,"id":"Q30361"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$58760A92-727C-478A-B544-E2F782DD52FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ff80b41d03c65073c007c903a317be0a9c94293e","datavalue":{"value":{"entity-type":"item","numeric-id":13958,"id":"Q13958"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$5C354A8C-7D65-4FB8-96F1-118F1A70501A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"4d7f4b76492a75780585d40fb718d00d42a05322","datavalue":{"value":{"entity-type":"item","numeric-id":19570,"id":"Q19570"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$92BD07C1-16CA-44CF-AC86-57EF22EDD956","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"4d81d02aeed8be60bec4eae0b793a8c2a2347a49","datavalue":{"value":{"entity-type":"item","numeric-id":46083,"id":"Q46083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$08422834-82BC-4641-A84F-F86ADB8CA58F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"583675b13be5f1d5d55e9f4b322cf50040e205b1","datavalue":{"value":{"entity-type":"item","numeric-id":44086,"id":"Q44086"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$18F0CAFB-6382-47A4-8A7D-A04C9230EFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"7be4145414c2429f47282433414c638de68f044e","datavalue":{"value":{"entity-type":"item","numeric-id":40904,"id":"Q40904"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$76EDCD26-C3EE-445B-B5E8-AFC7C1BE7661","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"67d5af6ef410bc7cf7f49a8833d90ef52e36c612","datavalue":{"value":{"entity-type":"item","numeric-id":20911,"id":"Q20911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$A1763B8B-0243-48FC-B6F8-490840E7D149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"448f73ce6516d86885ec170fdeef39cf34d07801","datavalue":{"value":{"entity-type":"item","numeric-id":51732,"id":"Q51732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$2256B6E4-59A9-4EA8-8780-C0C63E4033D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"bc63b18f29e81036c5e8291dd57d82490deaa954","datavalue":{"value":{"entity-type":"item","numeric-id":19233,"id":"Q19233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$9E0CBD1E-F4A0-4507-8D9A-952FEF041C6B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"27b35591f9a1d87570b3e9ffb19e51ff7cd09a28","datavalue":{"value":{"entity-type":"item","numeric-id":40544,"id":"Q40544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$D8325E68-5587-4999-8B37-E449E71B03D5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"95e5f1158f96f22279bdd9d9c26433e98a490641","datavalue":{"value":{"entity-type":"item","numeric-id":21498,"id":"Q21498"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$1A63316D-02CA-41CE-878B-5EEEBB29F7F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"fd1c0b3f068cc22555c5a8c14d4ac959e115ce60","datavalue":{"value":{"entity-type":"item","numeric-id":25201,"id":"Q25201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$B3523138-E737-4C98-A85F-694AB1F579ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"4eea1e5549472c93f3282a38917960fdec6b61a1","datavalue":{"value":{"entity-type":"item","numeric-id":24733,"id":"Q24733"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$53105165-87CB-4CDC-A9B3-2EF84750E8F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"f04f31c89e971a466739b17d1b0a4f1fdb9c0c1e","datavalue":{"value":{"entity-type":"item","numeric-id":26493,"id":"Q26493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$FC19C868-1B2D-4E2C-BBF2-43776EC27153","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"7ea0a87649edd4cae39bef36b6b305a729532abf","datavalue":{"value":{"entity-type":"item","numeric-id":39832,"id":"Q39832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$7373425A-4438-4ACD-8768-09D18DED3715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"7343f563fd02ee3f7d39ccb038f5c1c6c726769a","datavalue":{"value":{"entity-type":"item","numeric-id":20799,"id":"Q20799"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$AF47F256-4DB3-4E75-BE95-CDC667F3811B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1458","hash":"ab75a27745b95bbc51eed60e2ef7157b7c449125","datavalue":{"value":{"entity-type":"item","numeric-id":33768,"id":"Q33768"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$BB878097-B519-4D97-B7A5-3DCD9B70A028","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"830c59a2e64cb1b347b2e61a8b50382921902adf","datavalue":{"value":"https://isa-afp.org/entries/Knuth_Morris_Pratt.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q40965$C41E55D5-315C-4584-9B09-BFEE8F62D6E0","rank":"normal"}],"P43":[{"mainsnak":{"snaktype":"value","property":"P43","hash":"7367b16d2a7a3d3a354751cf4004ad9db8d21825","datavalue":{"value":"Fabian Hellauer","type":"string"},"datatype":"string"},"type":"statement","id":"Q40965$F93DA65A-C841-48B5-9991-BB2C7120EE95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P43","hash":"7545c5768cca6bd4b47e52bfec18c22cb81849df","datavalue":{"value":"Peter Lammich","type":"string"},"datatype":"string"},"type":"statement","id":"Q40965$B3DAB811-13E6-4FCA-AAE3-C00E8D22BE3F","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"55848613e228a509c7a35e96c21f2720128c093d","datavalue":{"value":"The Knuth-Morris-Pratt algorithm is often used to show that the problem of finding a string s in a text t can be solved deterministically in O(|s| + |t|) time. We use the Isabelle Refinement Framework to formulate and verify the algorithm. Via refinement, we apply some optimisations and finally use the Sepref tool to obtain executable code in Imperative/HOL .","type":"string"},"datatype":"string"},"type":"statement","id":"Q40965$59D1EF60-F37C-45AF-8705-80506BA19741","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9bd6b55577e7ffdb7837b8ca322f8a7d1011d8a1","datavalue":{"value":{"time":"+2017-12-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q40965$B7EDE117-2CB2-4DA0-A56C-80464C3DEB36","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"43a706250b8e964d17331dff1d6f6fc46a5d1eb9","datavalue":{"value":{"text":"The string search algorithm by Knuth, Morris and Pratt","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q40965$B7586040-A02C-4E92-8C45-4B9145D54F76","rank":"normal"}],"P223":[{"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":"Q40965$7E88177A-E49A-4D23-9170-3E9B6903C4ED","rank":"normal"}],"P37":[{"mainsnak":{"snaktype":"value","property":"P37","hash":"9a21a8eebe97539644aa32b24dda137c12e751dc","datavalue":{"value":{"entity-type":"item","numeric-id":40327,"id":"Q40327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$DDECE1A6-7C7F-49E2-B408-AF2415863A98","rank":"normal"}],"P585":[{"mainsnak":{"snaktype":"value","property":"P585","hash":"6df1e1600a3acc40d1b0a9c9cf7cbc177462ddf9","datavalue":{"value":{"entity-type":"item","numeric-id":7361373,"id":"Q7361373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$29A49B5A-C860-4C13-BFDE-D6029463168C","rank":"normal"}],"P2651":[{"mainsnak":{"snaktype":"value","property":"P2651","hash":"1157f6239d5752bb0ad1cee836272bd46c6bf40f","datavalue":{"value":{"entity-type":"item","numeric-id":7360772,"id":"Q7360772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q40965$748E258A-32EE-45AB-A4E8-8B2CBC574811","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Knuth Morris Pratt","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Knuth_Morris_Pratt"}}}}}