We consider the streaming complexity of a fundamental task in approximate pattern
matching: the k-mismatch problem. In this problem, we must compute Hamming distances …

We consider computing a longest palindrome in the streaming model, where the symbols
arrive one-by-one and we do not have random access to the input. While computing the …

A fundamental problem on strings in the realm of approximate string matching is pattern
matching with mismatches: Given a text t, a pattern p, and a number k, determine whether …

We study the problem of recognizing regular languages in a variant of the streaming model
of computation, called the sliding window model. In this model, we are given a size of the …

In the pattern matching with d wildcards problem one is given a text T of length n and a
pattern P of length m that contains d wildcard characters, each denoted by a special symbol …

In the k-mismatch problem we are given a pattern of length n and a text and must find all
locations where the Hamming distance between the pattern and the text is at most k. A …

We consider two well-known related problems: Longest Repeated Substring (LRS) and
Longest Repeated Reversed Substring (LRRS). Their streaming versions cannot be solved …

In many streaming applications recent elements in the stream are considered more
important than older elements. In the sliding window model we are given an unbounded …

We consider the problem of computing distance between a pattern of length $ n $ and all $ n
$-length subwords of a text in the streaming model. In the streaming setting, only the …