{"entities":{"Q2003324":{"pageid":2014066,"ns":120,"title":"Item:Q2003324","lastrevid":56828916,"modified":"2026-03-23T17:27:05Z","type":"item","id":"Q2003324","labels":{"en":{"language":"en","value":"Permuted pattern matching algorithms on multi-track strings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7077448"}},"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":"Q2003324$C6C4850A-35A8-4118-8A26-D0DCC698583E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4cba621194a7a7a934b0ed66f406f7085f45b2c1","datavalue":{"value":{"text":"Permuted pattern matching algorithms on multi-track strings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2003324$C0E603A4-8092-416F-AC18-CE15311FA8AD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"507339e85404aab53b26b08d3966ae4bdc905809","datavalue":{"value":"1461.68267","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003324$8E4E0C4B-C9C0-4883-811D-B4B7F2E0ACE3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a803e3f4b6673d706271e6ae9da73ea7f43bb622","datavalue":{"value":{"entity-type":"item","numeric-id":782169,"id":"Q782169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$64C33E2E-6F6A-4A53-BA55-04A37A05D6BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41e28125390659396321373e7938275849ae7021","datavalue":{"value":{"entity-type":"item","numeric-id":2003323,"id":"Q2003323"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$FFD37F3B-306D-4112-B106-5AA1163ABC90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9f1d21409d0d874feb1d6fa97f1cf8ed4e17ff22","datavalue":{"value":{"entity-type":"item","numeric-id":491145,"id":"Q491145"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$D587C4B9-191E-4E6B-A8E8-DFE0BCF124A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b89494e796aaafece25ab389513f0dcd4f6e3954","datavalue":{"value":{"entity-type":"item","numeric-id":249065,"id":"Q249065"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$205DCCEC-474C-4F85-AFB6-CE23A62CFD13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f919044541ff85168c0a049d263045de77e3a296","datavalue":{"value":{"entity-type":"item","numeric-id":496551,"id":"Q496551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$E03F02D5-CC11-4463-924B-90720F53FF07","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"18e3aed7ec2baba1bc6b2c08988b16bb9ac0e77f","datavalue":{"value":{"entity-type":"item","numeric-id":82263,"id":"Q82263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$443C67E7-4870-44D7-A8BC-D8537EBC5528","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"95484946e883fc7b4dd3685da23c3ff319dc5c53","datavalue":{"value":{"time":"+2019-07-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":"Q2003324$4B75D0B1-DA9A-4293-A967-33C9C4CDC417","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"01112b626ce7fd4925c52b6e31fe0eb104574bc1","datavalue":{"value":"Summary: A multi-track string is a tuple of strings of the same length. Given the pattern and text of two multi-track strings, the permuted pattern matching problem is to find the occurrence positions of all permutations of the pattern in the text. In this paper, we propose several algorithms for permuted pattern matching. Our first algorithm, which is based on the Knuth-Morris-Pratt (KMP) algorithm, has a fast theoretical computing time with \\(O(m k)\\) as the preprocessing time and \\(O(n k \\log \\sigma)\\) as the matching time, where \\(n\\), \\(m\\), \\(k\\), \\(\\sigma\\), and occ denote the length of the text, the length of the pattern, the number of strings in the multi-track, the alphabet size, and the number of occurrences of the pattern, respectively. We then improve the KMP-based algorithm by using an automaton, which has a better experimental running time. The next proposed algorithms are based on the Boyer-Moore algorithm and the Horspool algorithm that try to perform pattern matching. These algorithms are the fastest experimental algorithms. Furthermore, we propose an extension of the AC-automaton algorithm that can solve dictionary matching on multi-tracks, which is a task to find multiple multi-track patterns in a multi-track text. Finally, we propose filtering algorithms that can perform permuted pattern matching quickly in practice.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003324$F88D05A0-082B-4C7F-86B8-AD7EA5716ABF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"824c9242ee6f86c15bf4eecb8cafeab39e222c2d","datavalue":{"value":"68W32","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003324$DEFA9C93-6D43-434B-93A1-E996A1ADF48D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003324$7324F4F5-5196-42B8-89CE-C0ECD9C5FEEE","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3646c9e790e73402a157f062d9f8b41fb55bfd7","datavalue":{"value":"7077448","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003324$9924A8B1-B511-4D1A-8432-C5493E027F4B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"878f26f65af77090afa9d9bd6cd63991bf865e5f","datavalue":{"value":"multi-track string","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003324$8C4F8A02-FA4A-4092-B4F9-E8EA0A586EE2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"634760c2833c03e25f6aab5a2a1dfa55af8b6566","datavalue":{"value":"permuted pattern matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003324$FC7EC877-01D3-4E63-8558-2DD5F0B9750E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0b0403e57ee0bf87d07c45873096258553c0cdcd","datavalue":{"value":"AC-automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q2003324$984D63D9-6517-4679-9754-00FB93E7A01C","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":"Q2003324$B5CF7211-710A-4FC1-B1F8-4B36C1F2DE75","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f255c29c702b9739d60a3c3590e0ed02cc73b474","datavalue":{"value":"https://doi.org/10.3390/a12040073","type":"string"},"datatype":"url"},"type":"statement","id":"Q2003324$C95BF389-5DF3-4281-84CD-5E8D17CB86F2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"35a69766561f5a98a9534f293b18703859e9e9c1","datavalue":{"value":"W2936029001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003324$CFB8750E-98A7-4E2B-A123-EBCEE2F69C9E","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":"Q2003324$5F4A910F-4AE3-4054-ABDE-CBDBFEAAB10B","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":"Q2003324$4AFDB079-8F66-475F-B1ED-0F7BA2D02A23","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"765e1a7b0cd5402f72cc273dc87f1f94470d841f","datavalue":{"value":{"entity-type":"item","numeric-id":3142586,"id":"Q3142586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$ABB8B231-86FC-4C6D-8440-CA6ECA489AC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cef59b7464eee65c88a08785594b7606ba73e87","datavalue":{"value":{"entity-type":"item","numeric-id":533414,"id":"Q533414"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$325ED518-C980-4BBD-858D-E88F00DBF77F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fe7f31c55219fc9c5499c45ef11f89af004487c","datavalue":{"value":{"entity-type":"item","numeric-id":2927653,"id":"Q2927653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$3822343F-DCE4-4116-B594-77AFE2CB56D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81d7a9c125f343dcf1d068c27b5c61ad80868a4c","datavalue":{"value":{"entity-type":"item","numeric-id":5135244,"id":"Q5135244"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$C6E1CF16-5FE8-4E4B-BBFF-29ECCEF744ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a4cf7838a5d7b7802dfcd74891465f8d4fb476fd","datavalue":{"value":{"entity-type":"item","numeric-id":1796836,"id":"Q1796836"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$BB42D5AB-6842-4999-B456-AD90EC80CB5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27478db1b2fb5b4887454bf1a3d45a4f79eecf41","datavalue":{"value":{"entity-type":"item","numeric-id":507402,"id":"Q507402"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$F51144D6-8EAE-43FE-A587-AA436DD25F50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e884892508373839ae801c95d241a499a8aaf0a5","datavalue":{"value":{"entity-type":"item","numeric-id":4055184,"id":"Q4055184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$F3505FE3-3619-456A-80B1-053DC3E6968E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"65a1981a1203c79461c5c233d58fd88159a1e343","datavalue":{"value":{"entity-type":"item","numeric-id":3799643,"id":"Q3799643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$0DF3224A-424C-4D75-9139-E75A272E0D32","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"94fa1eac81fabb1dca93d77337bfd0199e598ffc","datavalue":{"value":{"entity-type":"item","numeric-id":4542583,"id":"Q4542583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2003324$2D4F7CCF-80FA-4590-B5C3-22104268F06D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"92d1966075e693d18e767d115469109f2802156b","datavalue":{"value":"10.3390/A12040073","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2003324$11998A6C-B981-421D-AC55-F80825EDA644","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9e0c281426bb28e2914919d87f05cd2eb94a2702","datavalue":{"value":{"entity-type":"item","numeric-id":2927653,"id":"Q2927653"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ef68b8a9a2923959343e14ed4b01342711ebdfd","datavalue":{"value":{"amount":"+0.9269939064979552","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":"Q2003324$6AF017D9-70EE-4496-8DE0-EFAA41AE16DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08e2f6ed48bc38511f72f0797c40e53cd2c0d4de","datavalue":{"value":{"entity-type":"item","numeric-id":834966,"id":"Q834966"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"36deecc1aeb1af37097b8cbad77de362a3a30862","datavalue":{"value":{"amount":"+0.7863662838935852","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":"Q2003324$A9177F12-9642-46F3-BB95-902154C1FF4B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ee1148b20da71032559921d0a10343593479b8a","datavalue":{"value":{"entity-type":"item","numeric-id":5393984,"id":"Q5393984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7207eb8e8ae718d8ae78cc0f8cadee9ba8a50815","datavalue":{"value":{"amount":"+0.7851055860519409","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":"Q2003324$51050367-0E6F-408B-8E71-9CB77E7F379D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1402dab4e522ba23c4ba9ca4b8c422bed2847bb8","datavalue":{"value":{"entity-type":"item","numeric-id":414411,"id":"Q414411"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c934a53dbaebcc6ab2d3027ef4587b628c2ae058","datavalue":{"value":{"amount":"+0.7598236799240112","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":"Q2003324$1FC70590-D905-48A7-B922-72C08E1DCCE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92927076bad95d6c457d71e1bb286cb70e8a19f2","datavalue":{"value":{"entity-type":"item","numeric-id":407548,"id":"Q407548"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5aa17e07c242d856a6eed80e4be4060fa2f44eab","datavalue":{"value":{"amount":"+0.7571204900741577","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":"Q2003324$889FCBB6-FD3C-4C8C-9DE3-6686B6107943","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":"Q2003324$E7FF8C46-C295-405E-ADB9-A75B53EE708A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2003324","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2003324"}}}}}