{"entities":{"Q688155":{"pageid":690004,"ns":120,"title":"Item:Q688155","lastrevid":63490062,"modified":"2026-04-11T13:30:43Z","type":"item","id":"Q688155","labels":{"en":{"language":"en","value":"Efficient detection of quasiperiodicities in strings"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 440331"}},"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":"Q688155$BB6CFE94-B444-4321-B6D8-500229B8958E","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b9d7ba9181a1d710cca87f65dae11e0b6bdd3d30","datavalue":{"value":{"text":"Efficient detection of quasiperiodicities in strings","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q688155$6F4035C0-9345-41B8-88D9-CAE86D310398","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d8e53ae4914e39c52954b3fdcc36a67ed75a109c","datavalue":{"value":"0804.68109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688155$EBB6E6D0-B1FE-4CCB-84A5-63CA063AD330","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"569bbec22678026a98e44b0859eb0340944d8cf2","datavalue":{"value":"10.1016/0304-3975(93)90159-Q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688155$87D1C7F2-05FB-4452-9C37-8A44A470CF83","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"873796445b5ce8d61b5ea73cdea0956f7aecf751","datavalue":{"value":{"entity-type":"item","numeric-id":294937,"id":"Q294937"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$ADB62957-FAD4-4546-AAEC-1C8FE1DC8FC5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d67134b63b86a737cbf981df8b43b8283dfbeaa9","datavalue":{"value":{"entity-type":"item","numeric-id":294724,"id":"Q294724"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$3873B44B-54E9-44EB-936A-40DCA69C0C35","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$37E53B65-B3FB-465B-9ED5-1BFB248A756F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9a56fa44f05f9c865c2049cda281119f7946a004","datavalue":{"value":{"time":"+1993-11-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q688155$207C5049-3512-4DEB-9B39-05DE49110564","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"f3d8299ccd6eb377dd5e46bfce4ce8345d6aecd3","datavalue":{"value":"A strings \\(z\\) is quasiperiodic if there is a string \\(w\\neq z\\) such that \\(z\\) is completely by (possibly overlapping) occurrences of \\(w\\) in \\(z\\). In this situation \\(w\\) is called a quasiperiod of \\(z\\). If \\(z\\) is quasiperiodic, then its shortest quasiperiod \\(w\\) is uniquely determined and is referred to as the quasiperiod of \\(z\\). (In this case \\(w\\) itself will not be quasiperiodic; such strings are called by the authors superprimitive. The problem addressed by this paper is to find maximal quasiperiodic substrings (and their quasiperiods) for a given string \\(x\\).   The main result is the construction of an algorithm to find all maximal quasiperiodic substrings of a given string \\(x\\) in time \\(O(n\\log^ 2 n)\\),where \\(n\\) is the length of \\(x\\).   The algorithm begins with the construction of a suffix tree for the given string \\(x\\). It then processes the tree in a bottom-up manner to discover, sort into appropriate lists, and test candidates for quasiperiodicities of \\(x\\). At the end of the process all maximal quasiperiodic substrings (and their quasiperiods) will have been discovered. A careful analysis of the structure of the suffix tree, of the actions to be performed during the processing, and of the data structures which will need to be maintained enable the authors to establish the \\(O(n\\log^ 2 n)\\) time bound and a linear space bound for the algorithm.","type":"string"},"datatype":"string"},"type":"statement","id":"Q688155$89C2E142-D370-4474-903B-8322BCB981AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688155$6C287A3C-404E-4057-833A-9E22C0B9917C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688155$6730302F-EFB4-403C-8EDB-EC3961CD16E8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e72b3d97c0ba63fe0a608c11dfdcd6a7dbbfcc72","datavalue":{"value":"440331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q688155$14ADDA75-3E58-4E06-8D66-2FEA704088E1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a9e74bb208f12a401b4ac31fbfb4bae2aad3f1b9","datavalue":{"value":"quasiperiods in strings","type":"string"},"datatype":"string"},"type":"statement","id":"Q688155$4CB68AC3-FE0E-4AB5-BC5F-71135D865220","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fee0973ae18f22fce0aaa0966efd47761d6ed525","datavalue":{"value":"periods in strings","type":"string"},"datatype":"string"},"type":"statement","id":"Q688155$97408080-F4C1-4218-BA39-62070CCC65BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7050345849300e1689cb28af1814bfe8177fe1b7","datavalue":{"value":"substring","type":"string"},"datatype":"string"},"type":"statement","id":"Q688155$4EE2A913-1042-4C19-9525-1CAC6BCDB9B4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7a747404b59b859f32425194571ad2a4a9cc4221","datavalue":{"value":{"entity-type":"item","numeric-id":1839320,"id":"Q1839320"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$32CAF238-FD05-421A-A99E-75651B2F325C","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":"Q688155$BCCDF429-97B8-47B0-A51B-E43402DCBA9E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"508f447d77bbad07f8e5e94e1b7b0a9223ed86d5","datavalue":{"value":{"entity-type":"item","numeric-id":3332275,"id":"Q3332275"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$0541CEB8-E248-4F4F-B5E0-DC17B1D8CB40","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b81d3e82ad72f9858e726462d8cf299aed08bca","datavalue":{"value":{"entity-type":"item","numeric-id":3690245,"id":"Q3690245"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$AAE416CC-0659-408F-A4C3-69FD22BEB7F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3c0ff434e60c254fe3625be605930aa47ce32d6e","datavalue":{"value":{"entity-type":"item","numeric-id":1194333,"id":"Q1194333"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$0E7101AE-4491-4CEF-B941-2ACC7EC6D24D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3d656ee44a323e749d5c6d4cf3e4b8271c3af114","datavalue":{"value":{"entity-type":"item","numeric-id":2542990,"id":"Q2542990"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$14639997-1D51-4065-9490-19709CE27133","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5cdbfdd739358918c257094ee918b71f56cfb78","datavalue":{"value":{"entity-type":"item","numeric-id":3746902,"id":"Q3746902"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$4E3D864B-AB89-4452-8728-485EAEBDBFBB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6f915a4d3b64d21c390c5b608317c503d87e6338","datavalue":{"value":{"entity-type":"item","numeric-id":1170893,"id":"Q1170893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$E28F2A59-9235-4C25-A9CF-439E61298D09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5388f39f2891ff1dd7515de4043950963f716caf","datavalue":{"value":{"entity-type":"item","numeric-id":1076522,"id":"Q1076522"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$D6BDBE19-72A6-430A-A7A3-4F689AD24F90","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68a4e203eb7c84092fa290a427adcc4cfb08285e","datavalue":{"value":{"entity-type":"item","numeric-id":5402537,"id":"Q5402537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$A9CE9681-DA5E-4ED4-9E22-F4A83266AF03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0bd5a7b1c56f611fd6356d090b7f7c8fee6b90d5","datavalue":{"value":{"entity-type":"item","numeric-id":1155963,"id":"Q1155963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$B905829C-33DB-4B34-B117-AA65027EB692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"242629057aa50cc359e5695d0642b188c96c72be","datavalue":{"value":{"entity-type":"item","numeric-id":3673134,"id":"Q3673134"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$3AC24A6A-E25D-4B7B-931E-5ABC5926B1C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"001860ad9c56eab4fac8c2ed4d07669adcfc57f2","datavalue":{"value":{"entity-type":"item","numeric-id":1177175,"id":"Q1177175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$E53B6418-6FDC-45CC-A6B8-12F47132ED6C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99627d0a96e3b61b0ecca4f33b58ced384cb3b50","datavalue":{"value":{"entity-type":"item","numeric-id":3315005,"id":"Q3315005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$A3906CBF-A7EE-437A-91E0-730D1D043FEE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8ab968868a27793512725f9615e172750ff9d631","datavalue":{"value":{"entity-type":"item","numeric-id":4529547,"id":"Q4529547"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$7BE084AB-6D92-472E-A4B5-254B76CDCD06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"55ca34fe94cbf494863af77ec148aceea3d9965b","datavalue":{"value":{"entity-type":"item","numeric-id":775458,"id":"Q775458"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$F408E442-6D70-4F17-B80B-E93DDA2797B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d542fa11c132f1cf082a7e35ae97bc38e66c51f","datavalue":{"value":{"entity-type":"item","numeric-id":3339319,"id":"Q3339319"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$CF29FFB5-F7CC-41BA-A677-C18E5408FD6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"81bcc2a2569a17c36782c1930dd1be0169c1c632","datavalue":{"value":{"entity-type":"item","numeric-id":3690246,"id":"Q3690246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$EDC18294-622B-4E39-936B-98D67F8AC25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4a2087c83c506735d7324c261f45643434228e51","datavalue":{"value":{"entity-type":"item","numeric-id":4095870,"id":"Q4095870"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$3D3CF719-95E4-4E62-8001-1AD83059E475","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f6121221f72e5fe22eeda454630edcacd7b029","datavalue":{"value":{"entity-type":"item","numeric-id":3741075,"id":"Q3741075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q688155$A1DABA52-95DD-4323-8111-2BCBB3563BC2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4e22dafc7b16faf0075387cb461d79736200281d","datavalue":{"value":{"entity-type":"item","numeric-id":2723969,"id":"Q2723969"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e5e2179e1752222d61c4cf6ede49838dd45dca0","datavalue":{"value":{"amount":"+0.9381916522979736","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":"Q688155$13CCC254-3975-4EF0-9FBF-3ADBA4746852","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01d74b98bbe277b26b0059b522932fcc278f43fe","datavalue":{"value":{"entity-type":"item","numeric-id":4503964,"id":"Q4503964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7d85555a9aa43422e919b8bbc4d370fb387bffc","datavalue":{"value":{"amount":"+0.9087100625038148","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":"Q688155$949F41E6-E15E-4AAF-BA17-1FE32A24B873","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"46caa28a43d7de00f54e6820d1e9df90796b99eb","datavalue":{"value":{"entity-type":"item","numeric-id":4939600,"id":"Q4939600"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc6ab1febd0a5e8c36b506a51e8c45452120bf2a","datavalue":{"value":{"amount":"+0.8898804783821106","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":"Q688155$E8BEB9B8-AAFC-4F00-9AA7-3E33F6C54F76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ea17abeee7b50716bc4c30ff5e7fb8f545bf7029","datavalue":{"value":{"entity-type":"item","numeric-id":1292493,"id":"Q1292493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cc6ab1febd0a5e8c36b506a51e8c45452120bf2a","datavalue":{"value":{"amount":"+0.8898804783821106","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":"Q688155$5AFC91F4-6119-45E8-B79E-BEAE1FF97EB1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4afe1a4fb677449664e1f4092c4a27bb3fa00ea4","datavalue":{"value":{"entity-type":"item","numeric-id":3809286,"id":"Q3809286"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f61b1ce408f5b608bbc7a156cc6c8c4b7effdbf6","datavalue":{"value":{"amount":"+0.8329306244850159","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":"Q688155$DE9BB2FE-FD28-4130-A43C-D8556EC0D4BA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient detection of quasiperiodicities in strings","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_detection_of_quasiperiodicities_in_strings"}}}}}