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.

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.

Maximal repetitions or runs in strings have a wide array of applications and thus have been extensively studied. In this paper, we extend this notion to 2-dimensions, precisely defining a maximal 2D repetition. We provide initial bounds on the number of maximal 2D repetitions that can occur in a matrix. The main contribution of this paper is the presentation of the first algorithm for locating all maximal 2D repetitions in a matrix. The algorithm is efficient and straightforward, with runtime O(n^2 log n log log n+ rho log n), where n^2 is the size of the input, and rho is the number of 2D repetitions in the output.

This paper extends the problem of palindrome searching into a higher dimension, addressing two definitions of 2D palindromes. The first definition implies a square, while the second definition (also known as a centrosymmetric factor), can be any rectangular shape. We describe two algorithms for searching a 2D text for maximal palindromes, one for each type of 2D palindrome. The first algorithm is optimal; it runs in linear time, on par with Manacher's linear time 1D palindrome algorithm. The second algorithm searches a text of size n_1 x n_2 (n_1 >= n_2) in O(n_2) time for each of its n_1 x n_2 positions. Since each position may have up to O(n_2) maximal palindromes centered at that location, the second result is also optimal in terms of the worst-case output size.

The dictionary matching problem seeks all locations in a given text that match any of the patterns in a given dictionary. Efficient algorithms for dictionary matching scan the text once, searching for all patterns simultaneously. Existing algorithms that solve the 2-dimensional dictionary matching problem all require working space proportional to the size of the dictionary. This paper presents the first efficient 2-dimensional dictionary matching algorithm that operates in small space. Given d patterns, D={P 1,…,P d }, each of size m×m, and a text T of size n×n, our algorithm finds all occurrences of P i , 1≤i≤d, in T. The preprocessing of the dictionary forms a compressed self-index of the patterns, after which the original dictionary may be discarded. Our algorithm uses O(dmlogdm) extra bits of space. The time complexity of our algorithm is close to linear, O(dm 2+n 2 τlogσ), where τ is the time it takes to access a character in the compressed self-index and σ is the size of the alphabet. Using recent results τ is at most sub-logarithmic.

MOTIVATION: A tandem repeat in DNA is a sequence of two or more contiguous, approximate copies of a pattern of nucleotides. Tandem repeats occur in the genomes of both eukaryotic and prokaryotic organisms. They are important in numerous fields including disease diagnosis, mapping studies, human identity testing (DNA fingerprinting), sequence homology and population studies. Although tandem repeats have been used by biologists for many years, there are few tools available for performing an exhaustive search for all tandem repeats in a given sequence. RESULTS: In this paper we describe an efficient algorithm for finding all tandem repeats within a sequence, under the edit distance measure. The contributions of this paper are two-fold: theoretical and practical. We present a precise definition for tandem repeats over the edit distance and an efficient, deterministic algorithm for finding these repeats. AVAILABILITY: The algorithm has been implemented in C++, and the software is available upon request and can be used at http://www.sci.brooklyn.cuny.edu/~sokol/trepeats. The use of this tool will assist biologists in discovering new ways that tandem repeats affect both the structure and function of DNA and protein molecules.

In this article, we address a new version of dynamic pattern matching. The dynamic text and static pattern matching problem is the problem of finding a static pattern in a text that is continuously being updated. The goal is to report all new occurrences of the pattern in the text after each text update. We present an algorithm for solving the problem where the text update operation is changing the symbol value of a text location. Given a text of length n and a pattern of length m , our algorithm preprocesses the text in time O ( n log log m ), and the pattern in time O ( m log m ). The extra space used is O ( n + m log m ). Following each text update, the algorithm deletes all prior occurrences of the pattern that no longer match, and reports all new occurrences of the pattern in the text in O (log log m ) time. We note that the complexity is not proportional to the number of pattern occurrences, since all new occurrences can be reported in a succinct form.

Two equal length strings s and s ′, over alphabets Σ s and Σ s ′, parameterize match if there exists a bijection π : Σ s → Σ s ′ such that π ( s ) = s ′, where π ( s ) is the renaming of each character of s via π. Parameterized matching is the problem of finding all parameterized matches of a pattern string p in a text t , and approximate parameterized matching is the problem of finding at each location a bijection π that maximizes the number of characters that are mapped from p to the appropriate | p |-length substring of t . Parameterized matching was introduced as a model for software duplication detection in software maintenance systems and also has applications in image processing and computational biology. For example, approximate parameterized matching models image searching with variable color maps in the presence of errors. We consider the problem for which an error threshold, k , is given, and the goal is to find all locations in t for which there exists a bijection π which maps p into the appropriate | p |-length substring of t with at most k mismatched mapped elements. Our main result is an algorithm for this problem with O ( nk 1.5 + mk log m ) time complexity, where m = | p | and n =| t |. We also show that when | p | = | t | = m , the problem is equivalent to the maximum matching problem on graphs, yielding a O ( m + k 1.5 ) solution.