{"@context":["https://w3id.org/fdo/context/v1",{"schema":"https://schema.org/","prov":"http://www.w3.org/ns/prov#","fdo":"https://w3id.org/fdo/vocabulary/"}],"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1268630","@type":"DigitalObject","kernel":{"@id":"https://fdo.portal.mardi4nfdi.de/fdo/Q1268630","digitalObjectType":"https://schema.org/ScholarlyArticle","primaryIdentifier":"mardi:Q1268630","kernelVersion":"v1","immutable":true,"modified":"2025-07-16T16:26:15Z"},"profile":{"@context":"https://schema.org","@type":"ScholarlyArticle","@id":"https://portal.mardi4nfdi.de/entity/Q1268630","name":"How many squares can a string contain?","headline":"How many squares can a string contain?","description":"scientific article; zbMATH DE number 1212932","url":"https://portal.mardi4nfdi.de/entity/Q1268630","datePublished":"1998-10-18","author":[{"@id":"https://portal.mardi4nfdi.de/entity/Q200918"},{"@id":"https://portal.mardi4nfdi.de/entity/Q686459"}],"publisher":[{"@id":"https://portal.mardi4nfdi.de/entity/Q171729"}],"identifier":{"@type":"PropertyValue","propertyID":"doi","value":"10.1006/JCTA.1997.2843","url":"https://doi.org/10.1006/JCTA.1997.2843"},"sameAs":["https://doi.org/10.1006/JCTA.1997.2843"],"comment":"Given a word over a fixed alphabet, a square is a subword of the form \\(uu= u^2\\) where \\(u\\) is a nonempty word. Denote by \\(M(n)\\) the maximum number of distinct squares (not translates of each other) possible in a word of length \\(n\\). Given the word \\(a_1a_2\\cdots a_n\\) let \\(s_i\\) be the number of squares beginning with \\(a_i\\) that do not appear later. The authors show \\(s_i\\leq 2\\), \\(1\\leq i\\leq n\\), and deduce that \\(M(n)< 2n\\) for all \\(n\\). Additionally, for infinitely many \\(n\\) it is shown that \\(M(n)= n- o(n)\\). Similar results are obtained for \\(P(n)\\), the maximum number of distinct primitive squares (\\(u\\) is not of the form \\(v^j\\), \\(j\\geq 2\\)) possible in a word of length \\(n\\).","citation":[{"@id":"https://portal.mardi4nfdi.de/entity/Q1155963"},{"@id":"https://portal.mardi4nfdi.de/entity/Q4849531"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1894296"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1394229"},{"@id":"https://portal.mardi4nfdi.de/entity/Q5340253"},{"@id":"https://portal.mardi4nfdi.de/entity/Q1346736"},{"@id":"https://portal.mardi4nfdi.de/entity/Q2253205"},{"@id":"https://portal.mardi4nfdi.de/entity/Q3659988"}]},"provenance":{"prov:generatedAtTime":"2025-07-16T16:26:15Z","prov:wasAttributedTo":"MaRDI Knowledge Graph"}}