This paper addresses the problem of identifying palindromic factors in texts that include wildcards - special characters that match all others. These symbols challenge many classical algorithms, as numerous combinatorial properties are not satisfied in their presence. We apply existing wildcard-LCE techniques to obtain a continuous time-memory tradeoff, and present the first non-trivial linear-space algorithm for computing all maximal palindromes with wildcards, improving the best known time-memory product in certain parameter ranges. Our main results are algorithms to find and approximate all maximal palindromes in a given text. We also generalize both methods to the k-mismatches setting, with or without wildcards.

File type classification is critical in digital forensics, and file carving. However, the increasing diversity of file formats challenges accurate classification. Traditional methods rely on hand-crafted features or compact neural networks but face long training times, limited training data, and lower accuracy. This paper introduces three novel, content-based file-type classification approaches to address these challenges. These approaches improve accuracy and streamline the integration of new file types using pre-trained models, enhancing both speed and reliability. The first approach utilizes Natural Language Processing (NLP) with a transformer architecture, while the second combines statistical features with a pre-trained model via transfer learning. These methods achieved accuracy rates of 72.4 % and 69.2 %, respectively, surpassing state-of-the-art Convolutional Neural Network (CNN) models. The third approach employs one-shot learning, achieving 100 % accuracy in several scenarios, enabling efficient training with minimal data.

A tandem repeat is an occurrence of two adjacent identical substrings. In this paper, we introduce the notion of a double string, which consists of two parallel strings, and we study the problem of locating all tandem repeats in a double string. The problem introduced here has applications beyond actual double strings, as we illustrate by solving two different problems with the algorithm of the double string tandem repeats problem. The first problem is that of finding all corner-sharing tandems in a 2-dimensional text, defined by Apostolico and Brimkov. The second problem is that of finding all scaled tandem repeats in a 1d text, where a scaled tandem repeat is defined as a string UU' such that U' is discrete scale of U. In addition to the algorithms for exact tandem repeats, we also present algorithms that solve the problem in the inexact sense, allowing up to k mismatches. We believe that this framework will open a new perspective for other problems in the future.

It is widely agreed that an introductory computer science (CS) course should be about more than just programming. Other aims are acquainting students with concepts and principles of CS and developing students' problem-solving skills. In this paper we propose an early introduction of a term often used by computer scientists: the Sliding Window (SW). The term has evolved over time among professionals to simplify the description of algorithms and can be used as well to support beginners when solving algorithmic problems. This metaphoric term enables abstracting and communicating ideas and at the same time it is easy to implement with elementary programming tools. We illustrate a set of stimulating problems in contemporary CS topics that use the SW and may be introduced in an introductory course.

We consider a class of pattern matching problems where a normalizing polynomial transformation can be applied at every alignment of the pattern and text. Normalized pattern matching plays a key role in fields as diverse as image processing and musical information processing, where application specific transformations are often applied to the input. By considering a wide range of such transformations, we provide fast algorithms and the first lower bounds for both new and old problems. Given a pattern of length $m$ and a longer text of length $n$, where both are assumed to contain integer values only, we first show $O(n\log m)$ time algorithms for pattern matching under linear transformations even when wildcard symbols can occur in the input. We then show how to extend the technique to polynomial transformations of arbitrary degree. Next we consider the problem of finding the minimum Hamming distance under polynomial transformation. We show that, for any $\varepsilon>0$, there cannot exist an $O(nm^{1-\varepsilon})$ time algorithm for additive and linear transformations conditional on the hardness of the classic 3Sum problem. Finally, we consider a version of the Hamming distance problem under additive transformations with a bound $k$ on the maximum distance that needs to be reported. We give a deterministic $O(nk\log k)$ time solution, which we then improve by careful use of randomization to $O(n\sqrt{k\log k}\log n)$ time for sufficiently small $k$. Our randomized solution outputs the correct answer at every position with high probability.

Multiple-interval graphs are a natural generalization of interval graphs where each vertex may have more then one interval associated with it. We initiate the study of optimization problems in multiple-interval graphs by considering three classical problems: Minimum Vertex Cover, Minimum Dominating Set, and Maximum Clique. We describe applications for each one of these problems, and then proceed to discuss approximation algorithms for them. Our results can be summarized as follows: Let t be the number of intervals associated with each vertex in a given multiple-interval graph. For Minimum Vertex Cover, we give a (2−1/ t )-approximation algorithm which also works when a t -interval representation of our given graph is absent. Following this, we give a t 2 -approximation algorithm for Minimum Dominating Set which adapts well to more general variants of the problem. We then proceed to prove that Maximum Clique is NP -hard already for 3-interval graphs, and provide a ( t 2 − t +1)/2-approximation algorithm for general values of t ≥ 2, using bounds proven for the so-called transversal number of t -interval families.