{"entities":{"Q1183603":{"pageid":1194352,"ns":120,"title":"Item:Q1183603","lastrevid":47057704,"modified":"2025-12-31T13:13:33Z","type":"item","id":"Q1183603","labels":{"en":{"language":"en","value":"Optimal canonization of all substrings of a string"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 33433"}},"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":"Q1183603$B4D10538-DD79-48A9-B88B-1F3440214ABF","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9857639665c68ce947383d668ef42371c4e2600e","datavalue":{"value":{"text":"Optimal canonization of all substrings of a string","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1183603$21F519C9-4A08-485F-8856-CB893581CD19","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"1c91cafb038003d5216305e9913c44cc956fb4b7","datavalue":{"value":"0757.68060","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183603$53974DD9-A78C-41E4-B64E-8E23120759A6","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"1709962c098872019f5baceeaff8b07913fc8608","datavalue":{"value":"10.1016/0890-5401(91)90016-U","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183603$CD5893E6-132A-4F9F-9A06-3D5516DC198D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"fa2d1ad91af9619c8dd37ab889fe279a84c4057e","datavalue":{"value":{"entity-type":"item","numeric-id":259032,"id":"Q259032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$56F3F29C-9CF6-45D7-9519-B6A04019A9A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"120787504bea9565def539fb4bfb19084956028b","datavalue":{"value":{"time":"+1992-06-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":"Q1183603$34A6E3BB-06AA-43D8-B9A2-F970C827AF67","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2a2f0df6420e906fe0e20ead4736239817738465","datavalue":{"value":"Let \\(\\Sigma\\) be a finite alphabet with total order \\(<\\). Extend \\(<\\) to \\(\\Sigma^ +\\) lexicographically by letting \\(x<y\\) iff for some \\(r,s,t,\\in\\Sigma^*\\) and \\(a,b\\in\\Sigma\\), \\(x=ras\\), \\(y=rbt\\), and \\(a<b\\). Let \\(x=s_ 1s_ 2\\dots s_ n\\in\\Sigma^ +\\). The \\(i\\)th rotation of \\(x\\) (\\(1\\leq i\\leq n\\)) is the string \\(w=s_ i\\dots s_ ns_ 1\\dots s_{i- 1}\\). The lexicographically smallest such rotation is called canonical.   The string \\(x\\in\\Sigma^ +\\) is called a Lyndon word if \\(x\\) is smaller than any of its proper suffixes. A Lyndon decomposition of \\(x\\in\\Sigma^ +\\) is the sequence \\((w_ 1\\dots w_ k)\\) of Lyndon words such that \\(x=w_ 1\\dots w_ k\\) and \\(w_ k\\leq w_{k-1}\\leq\\dots\\leq w_ 1\\).   The authors study the relationship between the Lyndon decomposition of \\(x\\) and its canonical rotation \\(w\\). Specifically, they characterize the Lyndon factor of \\(x\\) with which \\(w\\) must start. As an application, the authors develop faster on-line algorithms for finding the canonical rotations of a string. Also, fast incremental algorithms are presented which compute, in linear time, the canonical rotation of all prefixes of \\(x\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183603$03D120DD-9AC5-4000-B320-08400F8535F9","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":"Q1183603$28DA792E-F888-476E-9E8A-23E410ABD481","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183603$7F89B5FA-9777-4ABE-9BD1-9FE464C4F239","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"602b0a6cf84c3da627ef0121eed0c29ac871f42a","datavalue":{"value":"33433","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1183603$1ACADEA5-078E-46F1-98E4-9B19164AC486","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1f055a9e322124bb2b459bb0bdd4f348ffe085a7","datavalue":{"value":"Lyndon word","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183603$A75CC9A3-E72D-4509-B713-81301017B329","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7bd856795d2c64482dca4c519bb3dc875cf53d9","datavalue":{"value":"Lyndon decomposition","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183603$E1A51940-26A7-44DB-AFC0-8868E06F409F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"086e460855e38352738b7bb2d98a987f7b4064c4","datavalue":{"value":"rotation","type":"string"},"datatype":"string"},"type":"statement","id":"Q1183603$C551768F-FFC0-4B21-AA38-C3D27D768222","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":"Q1183603$B4B7DE76-7663-4F9C-8C1E-26B7761E95F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"e56b925a16fdea84cc9870575c5087cedee1d64d","datavalue":{"value":{"entity-type":"item","numeric-id":200906,"id":"Q200906"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$F263504F-E385-4A5C-AB94-E6F8D993E526","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":"Q1183603$CE9FC86F-3C70-4985-BDAD-7BBB286EFC16","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"340ea97c0f2f383d364057042ebc9f9438fcc85a","datavalue":{"value":{"entity-type":"item","numeric-id":4091421,"id":"Q4091421"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$D5F5BF49-447A-4ABB-9742-F8D2F99F0538","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2c8b99d441848e77082256c0ba387929c1cd319f","datavalue":{"value":{"entity-type":"item","numeric-id":1245010,"id":"Q1245010"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$72DA467A-5476-4A45-B4D7-19DE89997CBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9914f8121a32baf6895c6797ec99c63c32102968","datavalue":{"value":{"entity-type":"item","numeric-id":1242450,"id":"Q1242450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$679743FD-A699-47AC-B588-BF3188CBB15A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9c6798473d17b32e5cf11c451db3bb66e4a4c43c","datavalue":{"value":{"entity-type":"item","numeric-id":1144948,"id":"Q1144948"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$FD084DBC-E169-4E55-A727-5F09AD57E66D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1b0dbb5b4b782cb58543c829657352a03e93901b","datavalue":{"value":{"entity-type":"item","numeric-id":5895760,"id":"Q5895760"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$397EA83B-BEE2-463C-B249-FA600DC8A3DF","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":"Q1183603$E32AB434-2DB2-4D0A-8A8C-E369637C2A44","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":"Q1183603$6FA6B3CA-8B87-4BAE-8C63-262A72308441","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5d9c169b0618d1b4be087ea182382d9a1e2c175a","datavalue":{"value":{"entity-type":"item","numeric-id":4509227,"id":"Q4509227"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$0BBD2266-C92F-4586-85D3-B2C0146CCFC3","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":"Q1183603$D19EE3F8-DE97-4768-B399-31571553A1F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"160bb02f90deba1357b0546b9ef3f897898e1176","datavalue":{"value":{"entity-type":"item","numeric-id":1063420,"id":"Q1063420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$1EB6E7C6-91C2-4A36-8A30-EE300A0CD225","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"293c11927822a1dddc9045d337ec0663d922c1fa","datavalue":{"value":{"entity-type":"item","numeric-id":3910014,"id":"Q3910014"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1183603$BF94BF8E-4C3C-4050-8C98-484BA91D7872","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b84c73755a21c5bed40513529c1311c9b9ba4c76","datavalue":{"value":{"entity-type":"item","numeric-id":5369563,"id":"Q5369563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4a064006f30deb701bf848485dfa5eca7b0ae5e4","datavalue":{"value":{"amount":"+0.7901471257209778","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":"Q1183603$6DF6D46D-126E-4E1E-8B75-3F50EB253657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a189dcf4a453b30446f4f5ea49a6879bd2f2277b","datavalue":{"value":{"entity-type":"item","numeric-id":2922642,"id":"Q2922642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d45328326e1ea19a4e701ce2f9c45824ad1d535b","datavalue":{"value":{"amount":"+0.785669207572937","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":"Q1183603$D08FDDD5-5308-4712-B302-29FE038BA301","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2c7befcae10b5015c156b2d94ca4176ca604aa05","datavalue":{"value":{"entity-type":"item","numeric-id":4876360,"id":"Q4876360"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45f55cb047f2ac7414a29c586fab2785e675ba84","datavalue":{"value":{"amount":"+0.779373288154602","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":"Q1183603$627C4692-360A-4553-B864-A5CE6D8FCEC4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fcbf71a728b2400b7a5dd3067862964faaea5a56","datavalue":{"value":{"entity-type":"item","numeric-id":3315005,"id":"Q3315005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45f55cb047f2ac7414a29c586fab2785e675ba84","datavalue":{"value":{"amount":"+0.779373288154602","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":"Q1183603$C51BF8BB-746D-4EC4-8763-0B013A338326","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78525dafa42100e5f35d0732cbf54654dd87b23e","datavalue":{"value":{"entity-type":"item","numeric-id":4327381,"id":"Q4327381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2ce3e1918be1af6f3860134b0599ffa16d6aaec6","datavalue":{"value":{"amount":"+0.7731261849403381","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":"Q1183603$1AE06D4B-5C29-4121-8501-902EF29C16DC","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1183603","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1183603"}}}}}