Club utilise des cookies et des technologies similaires pour faire fonctionner correctement le site web et vous fournir une meilleure expérience de navigation.
Ci-dessous vous pouvez choisir quels cookies vous souhaitez modifier :
Club utilise des cookies et des technologies similaires pour faire fonctionner correctement le site web et vous fournir une meilleure expérience de navigation.
Nous utilisons des cookies dans le but suivant :
Assurer le bon fonctionnement du site web, améliorer la sécurité et prévenir la fraude
Avoir un aperçu de l'utilisation du site web, afin d'améliorer son contenu et ses fonctionnalités
Pouvoir vous montrer les publicités les plus pertinentes sur des plateformes externes
Club utilise des cookies et des technologies similaires pour faire fonctionner correctement le site web et vous fournir une meilleure expérience de navigation.
Ci-dessous vous pouvez choisir quels cookies vous souhaitez modifier :
Cookies techniques et fonctionnels
Ces cookies sont indispensables au bon fonctionnement du site internet et vous permettent par exemple de vous connecter. Vous ne pouvez pas désactiver ces cookies.
Cookies analytiques
Ces cookies collectent des informations anonymes sur l'utilisation de notre site web. De cette façon, nous pouvons mieux adapter le site web aux besoins des utilisateurs.
Cookies marketing
Ces cookies partagent votre comportement sur notre site web avec des parties externes, afin que vous puissiez voir des publicités plus pertinentes de Club sur des plateformes externes.
Une erreur est survenue, veuillez réessayer plus tard.
Il y a trop d’articles dans votre panier
Vous pouvez encoder maximum 250 articles dans votre panier en une fois. Supprimez certains articles de votre panier ou divisez votre commande en plusieurs commandes.
In this thesis, we study the following three types of periodic string patterns and some of their variants.Firstly, we consider maximal d-repetitions. These are substrings that are at least 2+d times as long as their minimum period.Secondly, we consider 3-cadences. These are arithmetic subsequence of three equal characters.Lastly, we consider maximal pairs. These are pairs of identical substrings.Maximal d-repetitions and maximal pairs of uncompressed strings are already well-researched. However, no non-trivial upper bound for distinct occurrences of these patterns that take the compressed size of the underlying strings into account were known prior to this research.We provide upper bounds for several variants of these two patterns that depend on the compressed size of the string, the logarithm of the string's length, the highest allowed power and d.These results also lead to upper bounds and new insights for the compacted directed acyclic word graph and the run-length encoded Burrows-Wheeler transform.We prove that cadences with three elements can be efficiently counted in uncompressed strings and can even be efficiently detected on grammar-compressed binary strings. We also show that even slightly more difficult variants of this problem are already NP-hard on compressed strings.Along the way, we extend the underlying geometry of the convolution from rectangles to arbitrary polygons. We also prove that this non-rectangular convolution can still be efficiently computed.