Tight Tradeoffs for Real-Time Approximation of Longest
Palindromes in Streams
Paweł Gawrychowski1 , Oleg Merkurev2 , Arseny M. Shur2 , and Przemysław Uznański3
1

arXiv:1610.03125v1 [] 10 Oct 2016

2

Institute of Informatics, University of Warsaw, Poland
Institute of Mathematics and Computer Science, Ural Federal University, Ekaterinburg,
Russia
3
Department of Computer Science, ETH Zürich, Switzerland
January 19, 2018
Abstract
We consider computing a longest palindrome in the streaming model, where the symbols arrive oneby-one and we do not have random access to the input. While computing the answer exactly using
sublinear space is not possible in such a setting, one can still hope for a good approximation guarantee.
Our contribution is twofold. First, we provide lower bounds on the space requirements for randomized
approximation algorithms processing inputs of length n. We rule out Las Vegas algorithms, as they
cannot achieve sublinear space complexity. For Monte Carlo algorithms, we prove a lower bounds of
Ω(M log min{|Σ|, M }) bits of memory; here M = n/E for approximating the answer with additive error
log n
for approximating the answer with multiplicative error (1 + ε). Second, we design
E, and M = log(1+ε)
three real-time algorithms for this problem. Our Monte Carlo approximation algorithms for both additive
and multiplicative versions of the problem use O(M ) words of memory. Thus the obtained lower bounds
are asymptotically tight up to a logarithmic factor. The third algorithm is deterministic and finds a
longest palindrome exactly if it is short. This algorithm can be run in parallel with a Monte Carlo
algorithm to obtain better results in practice. Overall, both the time and space complexity of finding a
longest palindrome in a stream are essentially settled.

1

Introduction

In the streaming model of computation, a very long input arrives sequentially in small portions and cannot
be stored in full due to space limitation. While well-studied in general, this is a rather recent trend in
algorithms on strings. The main goals are minimizing the space complexity, i.e., avoiding storing the already
seen prefix of the string explicitly, and designing real-time algorithm, i.e., processing each symbol in worstcase constant time. However, the algorithms are usually randomized and return the correct answer with
high probability. The prime example of a problem on string considered in the streaming model is pattern
matching, where we want to detect an occurrence of a pattern in a given text. It is somewhat surprising
that one can actually solve it using polylogarithmic space in the streaming model, as proved by Porat and
Porat [15]. A simpler solution was later given by Ergün et al. [6], while Breslauer and Galil designed a
real-time algorithm [3]. Similar questions studied in such setting include multiple-pattern matching [4],
approximate pattern matching [5], and parametrized pattern matching [10].
We consider computing a longest palindrome in the streaming model, where a palindrome is a fragment
which reads the same in both directions. This is one of the basic questions concerning regularities in texts
and it has been extensively studied in the classical non-streaming setting, see [1, 8, 12, 14] and the references
therein. The notion of palindromes, but with a slightly different meaning, is very important in computational
1

biology, where one considers strings over {A, T, C, G} and a palindrome is a sequence equal to its reverse
complement (a reverse complement reverses the sequences and interchanges A with T and C with G); see [9]
and the references therein for a discussion of their algorithmic aspects. Our results generalize to biological
palindromes in a straightforward manner.
We denote by LPS(S) the problem of finding the maximum length of a palindrome in a string S (and a
starting position of a palindrome of such length in S). Solving LPS(S) in the streaming model was recently
considered by Berenbrink et al. [2], who developed tradeoffs between the bound on the error and the space
complexity for additive and multiplicative variants of the problem, that is, for approximating the length of
the longest palindrome with either additive or multiplicative error. Their algorithms were Monte Carlo, i.e.,
returned the correct answer with high probability. They also proved that any Las Vegas algorithm achieving
n
log |Σ|) bits √
of memory, which matches the space complexity of
additive error E must necessarily use Ω( E
their solution up to a logarithmic factor in the E ∈ [1, n] range, but leaves a few questions. Firstly, does
the lower bound
√ still hold for Monte Carlo algorithms? Secondly, what is the best possible space complexity
when E ∈ ( n, n] in the additive variant, and what about the multiplicative version? Finally, are there
real-time algorithms achieving these optimal space bounds? We answer all these questions.
Our main goal is to settle the space complexity of LPS. We start with the lower bounds in Sect. 2.
First, we show that Las Vegas algorithms cannot achieve sublinear space complexity at all. Second, we
prove a lower bound of Ω(M log min{|Σ|, M }) bits of memory for Monte Carlo algorithms; here M = n/E
log n
for approximating the answer with
for approximating the answer with additive error E, and M = log(1+ε)
multiplicative error (1+ε). Then, in Sect. 3 we design real-time Monte Carlo algorithms matching these lower
bounds up to a logarithmic factor. More precisely, our algorithm for LPS with additive error E ∈ [1, n] uses
O(n/E) words of space, while our algorithms for LPS with multiplicative error ε ∈ (0, 1] (resp., ε ∈ (1, n])

log n
uses O log(nε)
(resp., O( log(1+ε)
)) words of space1 . Finally we present, for any m, a deterministic O(m)ε
space real-time algorithm solving LPS exactly if the answer is less than m and detecting a palindrome of
length ≥ m otherwise. The last result implies that if the input stream is fully random, then with high
probability its longest palindrome can be found exactly by a real-time algorithm within logarithmic space.
Notation and Definitions. Let S denote a string of length n over an alphabet Σ = {1, . . . , N }, where
N is polynomial in n. We write S[i] for the ith symbol of S and S[i..j] for its substring (or factor )
S[i]S[i+1] · · · S[j]; thus, S[1..n] = S. A prefix (resp. suffix ) of S is a substring of the form S[1..j] (resp.,
S[j..n]). A string S is a palindrome if it equals its reversal S[n]S[n−1] · · · S[1]. By L(S) we denote the length
of a longest palindrome which is a factor of S. The symbol log stands for the binary logarithm.
We consider the streaming model of computation: the input string S[1..n] (called the stream) is read left
to right, one symbol at a time, and cannot be stored, because the available space is sublinear in n. The
space is counted as the number of O(log n)-bit machine words. An algorithm is real-time if the number of
operations between two reads is bounded by a constant. An approximation algorithm for a maximization
problem has additive error E (resp., multiplicative error ε) if it finds a solution with the cost at least OP T −E
T
(resp., OP
1+ε ), where OP T is the cost of optimal solution; here both E and ε can be functions of the size of
the input. In the LPS(S) problem, OP T = L(S).
A Las Vegas algorithm always returns a correct answer, but its working time and memory usage on
the inputs of length n are random variables. A Monte Carlo algorithm gives a correct answer with high
probability (greater than 1 − 1/n) and has deterministic working time and space.

2

Lower Bounds

In this section we use Yao’s minimax principle [17] to prove lower bounds on the space complexity of the LPS
problem in the streaming model, where the length n and the alphabet Σ of the input stream are specified.
We denote this problem by LPSΣ [n].
1 Note that (a) log(1 + ε) is equivalent to ε whenever ε < 1; (b) the space used by the algorithms is O(n) for any values of
errors; (c) the multiplicative lower bound applies to ε > n−0.99 , and thus is not contradicting the algorithm space usage.

2

Theorem 2.1 (Yao’s minimax principle for randomized algorithms). Let X be the set of inputs for a problem
and A be the set of all deterministic algorithms solving it. Then, for any x ∈ X and A ∈ A, the cost of
running A on x is denoted by c(a, x) ≥ 0.
Let p be the probability distribution over A, and let A be an algorithm chosen at random according to p.
Let q be the probability distribution over X , and let X be an input chosen at random according to q. Then
maxx∈X E[c(A, x)] ≥ mina∈A E[c(a, X)].
We use the above theorem for both Las Vegas and Monte Carlo algorithms. For Las Vegas algorithms, we
consider only correct algorithms, and c(x, a) is the memory usage. For Monte Carlo algorithms, we consider
all algorithms (not necessarily correct) with memory usage not exceeding a certain threshold, and c(x, a) is
the correctness indicator function, i.e., c(x, a) = 0 if the algorithm is correct and c(x, a) = 1 otherwise.
Our proofs will be based on appropriately chosen padding. The padding requires a constant number of
fresh characters. If Σ is twice as large as the number of required fresh characters, we can still use half of
it to construct a difficult input instance, which does not affect the asymptotics. Otherwise, we construct a
difficult input instance over Σ, then add enough new fresh characters to facilitate the padding, and finally
reduce the resulting larger alphabet to binary at the expense of increasing the size of the input by a constant
factor.
Lemma 2.2. For any alphabet Σ = {1, 2, . . . , σ} there exists a morphism h : Σ∗ → {0, 1}∗ such that, for
any c ∈ Σ, |h(c)| = 2σ + 6 and, for any string w, w contains a palindrome of length ` if and only if h(w)
contains a palindrome of length (2σ + 6) · `.
Proof. We set:
h(c) = 11s 01s−c 10011s−c 01c 1.
Clearly |h(c)| = 2σ + 6 and, because every h(c) is a palindrome, if w contains a palindrome of length ` then
h(w) contains a palindrome of length (2σ + 6) · `. Now assume that h(w) contains a palindrome of length
(2σ + 6) · `, where ` ≥ 1. If ` = 1 then we obtain that w should contain a palindrome of length 1, which
always holds. Otherwise, the palindrome contains 00 inside and we consider two cases.
1. The palindrome is centered inside 00. Then it corresponds to an odd palindrome of length ` in w.
2. The palindrome maps some 00 to another 00. Then it corresponds to an even palindrome of length `
in w.
In either case, the claim holds.
For the padding we will often use an infinite string ν = 01 11 02 12 03 13 . . ., or more precisely its prefixes of
length d, denoted ν(d). Here 0 and 1 should be understood
√ as two characters not belonging to the original
alphabet. The longest palindrome in ν(d) has length O( d).
Theorem 2.3 (Las Vegas approximation). Let A be a Las Vegas streaming algorithms solving LPSΣ [n]
with additive error E ≤ 0.99n or multiplicative error (1 + ε) ≤ 100 using s(n) bits of memory. Then
E[s(n)] = Ω(n log |Σ|).
Proof. By Theorem 2.1, it is enough to construct a probability distribution P over Σn such that for any
deterministic algorithm D, its expected memory usage on a string chosen according to P is Ω(n log |Σ|) in
bits.
Consider solving LPSΣ [n] with additive error E. We define P as the uniform distribution over ν( E2 )x$$yν( E2 )R ,
0
where x, y ∈ Σn , n0 = n2 − E2 − 1, and $ is a special character not in Σ. Let us look at the memory usage of
0
D after having read ν( E2 )x. We say that x is “good” when the memory usage is at most n2 log |Σ| and “bad”
0
otherwise. Assume that 21 |Σ|n of all x’s are good, then there are two strings x 6= x0 such that the state of D
after having read both ν( E2 )x and ν( E2 )x0 is exactly the same. Hence the behavior of D on ν( E2 )x$$xR ν( E2 )R
and ν( E2 )x0 $$xR ν( E2 )R is exactly the same. The former is a palindrome of length n = 2n0 + E + 2, so D
must answer at least 2n0 + 2, and consequently the latter also must contain a palindrome of length at least
3

2n0 + 2. A palindrome inside ν( E2 )x0 $$xR ν( E2 )R is either fully contained within ν( E2 ), x0 , xR or it is a middle
√
palindrome. But the longest palindrome inside ν( E2 ) is of length O( E) < 2n0 + 2 (for n large enough) and
the longest palindrome inside x or xR is of length n0 < 2n0 + 2, so since we have exluced other possibilities,
ν( E2 )x0 $$xR ν( E2 )R contains a middle palindrome of length 2n0 + 2. This implies that x = x0 , which is a
0
contradiction. Therefore, at least 12 |Σ|n of all x’s are bad. But then the expected memory usage of D is at
0
least n4 log |Σ|, which for E ≤ 0.99n is Ω(n log |Σ|) as claimed.
Now consider solving LPSΣ [n] with multiplicative error (1 + ε). An algorithm with multiplicative error
ε
, so if the expected memory usage of such
(1 + ε) can also be considered as having additive error E = n · 1+ε
an algorithm is o(n log |Σ|) and (1 + ε) ≤ 100 then we obtain an algorithm with additive error E ≤ 0.99n
and expected memory usage o(n log |Σ|), which we already know to be impossible.
Now we move to Monte Carlo algorithms. We first consider exact algorithms solving LPSΣ [n]; lower
bounds on approximation algorithms will be then obtained by padding the input appropriately. We introduce
an auxiliary problem midLPSΣ [n], which is to compute the length of the middle palindrome in a string of
even length n over an alphabet Σ.
Lemma 2.4. There exists a constant γ such that any randomized Monte Carlo streaming algorithm A solving
midLPSΣ [n] or LPSΣ [n] exactly with probability 1 − n1 uses at least γ · n log min{|Σ|, n} bits of memory.
Proof. First we prove that if A is a Monte Carlo streaming algorithm solving midLPSΣ [n] exactly using less
1
than b n2 log |Σ|c bits of memory, then its error probability is at least n|Σ|
.
By Theorem 2.1, it is enough to construct probability distribution P over Σn such that for any deterministic algorithm D using less than b n2 log |Σ|c bits of memory, the expected probability of error on a string
1
chosen according to P is at least n|Σ|
.
Let n0 =

n
2.

0

For any x ∈ Σn , k ∈ {1, 2, . . . , n0 } and c ∈ Σ we define
w(x, k, c) = x[1]x[2]x[3] . . . x[n0 ]x[n0 ]x[n0 − 1]x[n0 − 2] . . . x[k + 1]c0k−1 .

Now P is the uniform distribution over all such w(x, k, c).
0
Choose an arbitrary maximal matching of strings from Σn into pairs (x, x0 ) such that D is in the same
state after reading either x or x0 . At most one string per state of D is left unpaired, that is at most
0
0
n
n
2b 2 log |Σ|c−1 strings in total. Since there are |Σ|n = 2n log |Σ| ≥ 2 · 2b 2 log |Σ|c−1 possible strings of length n0 ,
at least half of the strings are paired. Let s be longest common suffix of x and x0 , so x = vcs and x0 = v 0 c0 s,
where c 6= c0 are single characters. Then D returns the same answer on w(x, n0 − |s|, c) and w(x0 , n0 − |s|, c),
even though the length of the middle palindrome is exactly 2|s| in one of them, and at least 2|s| + 2 in the
other one. Therefore, D errs on at least one of these two inputs. Similarly, it errs on either w(x, n0 − |s|, c0 )
1
or w(x, n0 − |s|, c0 ). Thus the error probability is at least 2n01|Σ| = n|Σ|
.
Now we can prove the lemma for midLPSΣ [n] with a standard amplification trick. Say that we have
a Monte Carlo streaming algorithm, which solves midLPSΣ [n] exactly with error probability ε using s(n) bits
of memory. Then we can run its k instances simultaneously and return the most frequently reported answer.
The new algorithm needs O(k · s(n)) bits of memory and its error probability εk satisfies:
X k 
εk ≤
(1 − ε)i εk−i ≤ 2k · εk/2 = (4ε)k/2 .
i
2i<k

log(4/n)
1−o(1)
log n
1
= 61 1+log
Let us choose κ = 61 log(1/(n|Σ|))
|Σ|/ log n = Θ( log n+log |Σ| ) = γ · log |Σ| log min{|Σ|, n}, for some
constant γ. Now we can prove the
Assume that A uses less than κ · n log |Σ| = γ · n log min{|Σ|, n}
 1 theorem.
1
bits of memory. Then running 2κ
≥ 34 2κ
(which holds since κ < 16 ) instances of A in parallel requires less
than b n2 log |Σ|c bits of memory. But then the error probability of the new algorithm is bounded from above
by
3
  16κ

 18
16
4
1
1
=
≤
n
n|Σ|
n|Σ|

4

which we have already shown to be impossible.
The lower bound for midLPSΣ [n] can be translated into a lower bound for solving LPSΣ [n] exactly by
padding the input so that the longest palindrome is centered in the middle. Let x = x[1]x[2] . . . x[n] be the
input for midLPSΣ [n]. We define
w(x) = x[1]x[2]x[3] . . . x[n/2]1 000 . . . 0 1x[n/2 + 1] . . . x[n].
n

Now if the length of the middle palindrome in x is k, then w(x) contains a palindrome of length at least
n + k + 2. In the other direction, any palindrome inside w(x) of length ≥ n must be centered somewhere in
the middle block consisting of only zeroes and both ones are mapped to each other, so it must be the middle
palindrome. Thus, the length of the longest palindrome inside w(x) is exactly n + k + 2, so we have reduced
solving midLPSΣ [n] to solving LPSΣ [2n + 2]. We already know that solving midLPSΣ [n] with probability
1
≥ 1 − n1
1 − n1 requires γ · n log min{|Σ|, n} bits of memory, so solving LPSΣ [2n + 2] with probability 1 − 2n+2
0
requires γ · n log{|Σ|, n} ≥ γ · (2n + 2) log min{|Σ|, 2n + 2} bits of memory. Notice that the reduction needs
O(log n) additional bits of memory to count up to n, but for large n this is much smaller than the lower
bound if we choose γ 0 < γ4 .
To obtain a lower bound for Monte Carlo additive approximation, we observe that any algorithm solving
E
LPSΣ [n] with additive error E can be used to solve LPSΣ [ n−E
E+1 ] exactly by inserting 2 zeroes between every
two characters, in the very beginning, and in the very end. However, this reduction requires log( E2 ) ≤ log n
additional bits of memory for counting up to E2 and cannot be used when the desired lower bound on the
n
n
log min(|Σ|, E
) is significantly smaller than log n. Therefore, we need a separate
required number of bits Ω( E
technical lemma which implies that both additive and multiplicative approximation with error probability
1
n require Ω(log n) bits of space.
Lemma 2.5. Let A be any randomized Monte Carlo streaming algorithm solving LPSΣ [n] with additive error
at most 0.99n or multiplicative error at most n0.49 and error probability n1 . Then A uses Ω(log n) bits of
memory.
Proof. By Theorem 2.1, it is enough to construct a probability distribution P over Σn , such that for any
deterministic algorithm D using at most s(n) = o(log n) bits of memory, the expected probability of error
1
on a string chosen according to P is 2s(n)+2
.
0
n0
Let n = s(n) + 1. For any x, y ∈ Σ , let w(x, y) = ν( n2 − n0 )R xy R ν( n2 − n0 ). Observe that if x = y then
w(x, y) contains
a palindrome
of length n, and otherwise the longest palindrome there has length at most
√
√
2n0 + O( n) = O( n), thus any algorithm with additive error of at most 0.99n or with a multiplicative
error at most n0.49 must be able to distinguish between these two cases (for n large enough).
0
Let S ⊆ Σn be an arbitrary family of strings of length n0 such that |S| = 2 · 2s(n) , and let P be the
uniform distribution on all strings of the form w(x, y), where x and y are chosen uniformly and independently
0
from S. By a counting argument, we can create at least |S|
4 pairs (x, x ) of elements from S such that the
state of D is the same after having read ν( n2 − n0 )R x and ν( n2 − n0 )R x0 . (If we create the pairs greedily, at
most one such x per state of memory can be left unpaired, so at least |S| − 2s(n) = |S|
2 elements are paired.)
Thus, D cannot distinguish between w(x, x0 ) and w(x, x), and between w(x0 , x0 ) and w(x0 , x), so its error
1
1
probability must be at least |S|/2
|S|2 = 4·2s(n) . Thus if s(n) = o(log n), the error rate is at least n for n large
enough, a contradiction.
Combining the reduction with the technical lemma and taking into account that we are reducing to a
n
problem with string length of Θ( E
), we obtain the following.
Theorem 2.6 (Monte Carlo additive approximation). Let A be any randomized Monte Carlo streaming algorithm solving LPSΣ [n] with additive error E with probability 1 − n1 . If E ≤ 0.99n then A uses
n
n
Ω( E
log min{|Σ|, E
}) bits of memory.

5

n
Proof. Define σ = min{|Σ|, E
}.
n
Because of Lemma 2.5 it is enough to prove that Ω( E
log σ) is a lower bound when

E≤

n
γ
·
log σ.
2 log n

(1)

Assume that there is a Monte Carlo streaming algorithm A solving LPSΣ [n] with additive error E using
n
n
o( E
log σ) bits of memory and probability 1 − n1 . Let n0 = n−E/2
E/2+1 ≥ E (the last inequality, equivalent
E
to n ≥ E · E−2 holds because E ≤ 0.99n and because we can assume that E ≥ 200). Given a string
x[1]x[2] . . . x[n0 ], we can simulate running A on 0E x[1]0E/2 x[2]0E/2jx[3] . . . k0E/2 x[n0 ]0E/2 to calculate R (using
log(E/2) ≤ log n additional bits of memory), and then return

R
E/2+1

. We call this new Monte Carlo

0

streaming algorithm A . Recall that A reports the length of the longest palindrome with additive error E.
Therefore, if the original string contains a palindrome of length r, the new string contains a palindrome
of length E2 · (r + 1) + r, so R ≥ r(E/2 + 1) and A0 will return at least r. In the other direction, if A0
returns r, then the new string contains a palindrome of length r(E/2 + 1). If such palindrome is centered
so that x[i] is matched with x[i + 1] for some i, then it clearly corresponds to a palindrome of length r
in the original string. But otherwise every x[i] within the palindrome is matched with 0, so in fact the
whole palindrome corresponds to a streak of consecutive zeroes in the new string and can be extended to
the left and to the right to start and end with 0E , so again it corresponds to a palindrome of length r in
1
≥ 1 − n10 and
the original string. Therefore, A0 solves LPSΣ [n0 ] exactly with probability 1 − (n0 (E/2+1)+E/2)
0

uses o( n (E/2+1)+E/2
log σ) + log n = o(n0 log σ) + log n bits of memory. Observe that by Lemma 2.4 we get
E/2
a lower bound
γ
γ n
γ
γ · n0 log min{|Σ|, n0 } ≥ · n0 log σ + · log σ ≥ · n0 log σ + log n
2
2 E
2
(where the last inequality holds because of Eq.(1)). Then, for large n we obtain contradiction as follows
o(n0 log σ) + log n <

γ 0
· n log σ + log n.
2

Finally, we consider multiplicative approximation. The proof follows the same basic idea as of Theorem 2.6, however is more technically involved. The main difference is that due to uneven padding, we are
reducing to midLPSΣ [n0 ] instead of LPSΣ [n0 ].
Theorem 2.7 (Monte Carlo multiplicative approximation). Let A be any randomized Monte Carlo streaming
algorithm solving LPSΣ [n] with multiplicative error (1 + ε) with probability 1 − n1 . If n−0.98 ≤ ε ≤ n0.49 then
log n
log n
A uses Ω( log(1+ε)
log min{|Σ|, log(1+ε)
}) bits of memory.
Proof. For ε ≥ n0.001 the claimed lower bound reduces to Ω(1) bits, which obviously holds. Thus we can
assume that ε < n0.001 . Define
1
log n
− 2}.
σ = min{|Σ|,
50 log(1 + 2ε)
log n
First we argue that it is enough to prove that A uses Ω( log(1+ε)
log σ) bits of memory. Since log(1 + 2ε) ≤
0.001 log n + o(log n), we have that:

1
log n
− 2 ≥ 18 − o(1)
50 log(1 + 2ε)

(2)

1
log n
log n
− 2 = Θ(
).
50 log(1 + 2ε)
log(1 + 2ε)

(3)

log(1 + 2ε) = Θ(log(1 + ε))

(4)

and consequently:

Finally, observe that:

6

because log 2(1 + ε) = Θ(log(1 + ε)) for ε ≥ 1, and log(1 + ε) = Θ(ε) for ε < 1. From (3) and (4) we conclude
that:
log n
}).
(5)
log σ = Θ(log min{|Σ|,
log(1 + ε)
log n
Because of Lemma 2.5 and equations (4) and (5), it is enough to prove that Ω( log(1+ε)
log σ) is a lower
bound when
log σ
log(1 + 2ε) ≤ γ ·
,
(6)
100
log n
log n
as otherwise Ω( log(1+ε)
log σ) = Ω( log(1+2ε)
log σ) = Ω(log n).
Assume that there is a Monte Carlo streaming algorithm A solving LPSΣ [n] with multiplicative error
log n
(1+ε) with probability 1− n1 using o( log(1+ε)
log σ) bits of memory. Let x = x[1]x[2] . . . x[n0 ]x[n0 +1] . . . x[2n0 ]
0

be an input for midLPSΣ [2n0 ]. We choose n0 so that n = (1 + 2ε)n +1 · n0.99 . Then n0 = log(1+2ε) (n0.01 ) − 1 =
log n
1
d+1
0
· n0.99 e for any 0 ≤ d ≤ n0 .
100 log(1+2ε) − 1. We choose i0 , i1 , i2 , i3 , . . . , in so that i0 + . . . + id = d(1 + 2ε)
−0.98
0.99
0.01
(Observe that for ε = Ω(n
) we have i0 > n
and i1 , . . . , id > 2n
− 1.) Finally we define:
w(x) = ν(in0 )R x[1]ν(in0 −1 )R . . . x[n0 ]ν(i0 )R ν(i0 )x[n0 + 1]ν(i1 ) . . . ν(in0 −1 )x[2n0 ]ν(in0 ).
If x contains a middle palindrome of length exactly 2k, then w(x) contains a middle palindrome of length
2(1 + 2ε)k+1 · n0.99√
. Also, based on the properties of ν, any non-middle centered palindrome in w(x) has
length at most O( n), which is less than n0.99 for n large enough. Since d2(1 + 2ε)k · n0.99 e · (1 + ε) <
(2(1 + 2ε)k · n0.99 + 1) · (1 + ε) < 2(1 + 2ε)k+1 · n0.99 , value of k can be extracted from the answer of A. Thus,
if A approximates the middle palindrome in w(x) with multiplicative error (1 + ε) with probability 1 − n1
log n
using o( log(1+ε)
log σ) bits of memory, we can construct a new algorithm A0 solving midLPSΣ [2n0 ] exactly
1
with probability 1 − n1 > 1 − 2n
0 using
o(

log n
log σ) + log n
log(1 + ε)

(7)

bits of memory. By Lemma 2.4 we get a lower bound
γ · 2n0 log min{|Σ|, 2n0 }

=
≥

γ
log n
·
log σ − 2γ log σ
50 log(1 + 2ε)
γ
log n
·
log σ + log n − 2γ log σ
100 log(1 + 2ε)

(8)

(where the last inequality holds because of (6)). On the other hand, for large n


γ
log n
log n
1
·
log
σ
−
2γ
log
σ
+
log
n
=
−
2
γ log σ + log n
100 log(1+2ε)
100 log(1+2ε)


log n
log σ + log n
= Θ log(1+ε)
so (8) exceeds (7), a contradiction.

3

Real-Time Algorithms

In this section we design real-time Monte Carlo algorithms within the space bounds matching the lower
bounds from Sect. 2 up to a factor bounded by log n. The algorithms make use of the hash function known
as the Karp-Rabin fingerprint [11]. Let p be a fixed prime from the range [n3+α , n4+α ] for some α > 0, and
r be a fixed integer randomly chosen from {1, . . . , p−1}. For a string S, its forward hash and reversed hash
are defined, respectively, as
!
!
n
n
X
X
F
i
R
n−i+1
φ (S) =
S[i] · r mod p and φ (S) =
S[i] · r
mod p .
i=1

i=1

7

Clearly, the forward hash of a string coincides with the reversed hash of its reversal. Thus, if u is a palindrome,
then φF (u) = φR (u). The converse is also true modulo the (improbable) collisions of hashes, because for two
strings u 6= v of length m, the probability that φF (u) = φF (v) is at most m/p. This property allows one to
detect palindromes with high probability by comparing hashes. (This approach is somewhat simpler than the
one of [2]; in particular, we do not need “fingerprint pairs” used there.) In particular, a real-time algorithm
makes O(n) comparisons and thus faces a collision with probability O(n−1−α ) by the choice of p. All further
considerations assume that no collisions happen. For an input stream S, we denote F F (i, j) = φF (S[i..j])
and F R (i, j) = φR (S[i..j]). The next observation is quite important.
Proposition 3.1 ( [3]). The following equalities hold:

F F (i, j) = r−(i−1) F F (1, j) − F F (1, i−1) mod p ,
F R (i, j) = F R (1, j) − rj−i+1 F R (1, i−1) mod p .
Let I(i) denote the tuple (i, F F (1, i−1), F R (1, i−1), r−(i−1) mod p, ri mod p). The proposition below is
immediate from definitions and Proposition 3.1.
Proposition 3.2. 1) Given I(i) and S[i], the tuple I(i+1) can be computed in O(1) time.
2) Given I(i) and I(j+1), the string S[i..j] can be checked for being a palindrome in O(1) time.

3.1

Additive Error

Theorem 3.3. There is a real-time Monte Carlo algorithm solving the problem LPS(S) with the additive
error E = E(n) using O(n/E) space, where n = |S|.
First we present a simple (and slow) algorithm which solves the posed problem, i.e., finds in S a palindrome
of length `(S) ≥ L(S) − E, where L(S) is the length of the longest palindrome in S. Later this algorithm will
be converted into a real-time one. We store the sets I(j) for some values of j in a doubly-linked list SP in
the decreasing order of j’s. The longest palindrome currently found is stored as a pair answer = (pos, len),
where pos is its initial position and len is its length. Let tE = b E2 c.
In Algorithm ABasic we add I(j) to the list SP for each j divisible by tE . This allows us to check for
palindromicity, at ith iteration, all factors of the form S[ktE ..i]. We assume throughout the section that at
the beginning of ith iteration the value I(i) is stored in a variable I.
Algorithm 1 : Algorithm ABasic, ith iteration
1: if i mod tE = 0 then
2:
add I to the beginning of SP
3: read S[i]; compute I(i + 1) from I; I ← I(i + 1)
4: for all elements v of SP do
5:
if S[v.i..i] is a palindrome and answer.len < i−v.i+1 then
6:
answer ← (v.i, i−v.i+1)
Proposition 3.4. Algorithm ABasic finds in S a palindrome of length `(S) ≥ L(S) − E using O(n/E) time
per iteration and O(n/E) space.
Proof. Both the time and space bounds arise from the size of the list SP , which is bounded by n/tE =
O(n/E); the number of operations per iteration
 isproportional to this size due to Proposition 3.2. Now let
S[i..j] be a longest palindrome in S. Let k = tiE tE . Then i ≤ k < i + tE . At the kth iteration, I(k) was
added to SP ; then the palindrome S[k..j−(k−i)] was found at the iteration j − (k − i). Its length is
jE k
j − (k − i) − k + 1 = j − i − 2(k − i) + 1 > (j − i + 1) − 2tE = L(S) − 2
≥ L(S) − E,
2
as required.
8

The resource to speed up Algorithm ABasic stems from the following
Lemma 3.5. During one iteration, the length answer.len increases by at most 2 · tE .
Proof. Let S[j..i] be the longest palindrome found at the ith iteration. If i − j + 1 ≤ 2tE then the statement
is obviously true. Otherwise the palindrome S[j+tE ..i−tE ] of length i − j + 1 − 2tE was found before (at
the (i−tE )th iteration), and the statement holds again.
Lemma 3.5 implies that at each iteration SP contains only two elements that can increase answer.len.
Hence we get the following Algorithm A.
Algorithm 2 : Algorithm A, ith iteration
1: if i mod tE = 0 then
2:
add I to the beginning of SP
3:
if i = tE then
4:
sp ← f irst(SP )
5: read S[i]; compute I(i + 1) from I; I ← I(i + 1)
6: sp ← previous(sp)
7: while i − sp.i + 1 ≤ answer.len and (sp 6= last(SP )) do
8:
sp ← next(sp)
9: for all existing v in {sp, next(sp)} do
10:
if S[v.i..i] is a palindrome and answer.len < i−v.i+1 then
11:
answer ← (v.i, i−v.i+1)

. if exists

Due to Lemma 3.5, the cycle at lines 9–11 of Algorithm A computes the same sequence of values of
answer as the cycle at lines 4–6 of Algorithm ABasic. Hence it finds a palindrome of required length by
Proposition 3.4. Clearly, the space used by the two algorithms differs by a constant. To prove that an
iteration of Algorithm A takes O(1) time, it suffices to note that the cycle in lines 7–8 performs at most two
iterations. Theorem 3.3 is proved.

3.2

Multiplicative Error for ε ≤ 1

Theorem 3.6. There is a real-time Monte Carlo algorithm solving the problem LPS(S) with multiplicative

error ε = ε(n) ∈ (0, 1] using O log(nε)
space, where n = |S|.
ε
As in the previous section, we first present a simpler algorithm MBasic with non-linear working time and
then upgrade it to a real-time algorithm. The algorithm must find a palindrome of length `(S) ≥ L(S)
1+ε . The
next lemma is straightforward.
Lemma 3.7. If ε ∈ (0, 1], the condition `(S) ≥ L(S)(1 − ε/2) implies `(S) ≥ L(S)
1+ε .


We set qε = log 2ε . The main difference in the construction of algorithms with the multiplicative and
additive error is that here all sets I(i) are added to the list SP , but then, after a certain number of steps,
are deleted from it. The number of iterations the set I(i) is stored in SP is determined by the time-to-live
function ttl (i) defined below. This function is responsible for both the correctness of the algorithm and the
space bound.
Let β(i) be the position of the rightmost 1 in the binary representation of i (the position 0 corresponds
to the least significant bit). We define
ttl (i) = 2qε +2+β(i) .
(9)
The definition is illustrated by Fig. 1. Next we state a few properties of the list SP .
Lemma 3.8. For any integers a ≥ 1 and b ≥ 0, there exists a unique integer j ∈ [a, a + 2b ) such that
ttl (j) ≥ 2qε +2+b .
9

Algorithm 3 : Algorithm MBasic, ith iteration
1: add I to the beginning of SP
2: for all v in SP do
3:
if v.i + ttl (v.i) = i then
4:
delete v from SP
5: read S[i]; compute I(i + 1) from I; I ← I(i + 1)
6: for all v in SP do
7:
if S[v.i..i] is a palindrome and answer.len < i−v.i+1 then
8:
answer ← (v.i, i−v.i+1)
1

8

16

21

24

28

32

36

38 40 42 44

46

53

Figure 1: The state of the list SP after the iteration i = 53 (qε = 1 is assumed). Black squares indicate the
numbers j for which I(j) is currently stored. For example, (9) implies ttl (28) = 21+2+2 = 32, so I(28) will
stay in SP until the iteration 28 + 32 = 60.
Proof. By (9), ttl (j) ≥ 2qε +2+b if and only if β(j) ≥ b, i.e., j is divisible by 2b by the definition of β. Among
any 2b consecutive integers, exactly one has this property.
Figure 1 shows the partition of the range (0, i] into intervals having lengths that are powers of 2 (except
for the leftmost interval). In general, this partition consists of the following intervals, right to left:
l
n m
(i − 2qε +2 , i], (i − 2qε +3 , i − 2qε +2 ], . . . , (i − 2m , i − 2m−1 ], (0, i − 2m ], where m = log qε +2 − 1. (10)
2
Lemma 3.8 and (9) imply the following lemma on the distribution of the elements of SP .
Lemma 3.9. After each iteration, the first interval (resp., the last interval; each of the remaining intervals)
in (10) contains 2qε +2 (resp., at most 2qε +1 ; exactly 2qε +1 ) elements of the list SP .
The number of the intervals in (10) is O(log(nε)), so from Lemma 3.9 and the definition of qε we have
the following.

Lemma 3.10. After each iteration, the size of the list SP is O log(nε)
.
ε
Proposition 3.11. Algorithm MBasic finds a palindrome of length `(S) ≥

L(S)
1+ε

using O( log(nε)
) time per
ε

iteration and O( log(nε)
) space.
ε
Proof. Both the time per iteration and the space are dominated by the size of the list SP . Hence the required
complexity bounds follow from Lemma 3.10. For the proof of correctness, let S[i..j] be a palindrome of length
L(S). Further, let d = blog L(S)c.
If d < qε + 2, the palindrome S[i..j] will be found exactly, because I(i) is in SP at the jth iteration:
i + ttl (i) ≥ i + 2qε +2 ≥ i + 2d+1 > i + L(S) > j .
Otherwise, by Lemma 3.8 there exists a unique k ∈ [i, i + 2d−qε −1 ) such that ttl (k) ≥ 2d+1 . Hence at the
iteration j −(k −i) the palindrome S[i+(k−i)..j−(k−i)] will be found, because I(k) is in SP at this iteration:
k + ttl (k) ≥ i + ttl (k) ≥ i + 2d+1 > j ≥ j − (k − i) .
The length of this palindrome satisfies the requirement of the proposition:
j − (k − i) − (i + (k − i)) + 1 = L(S) − 2(k − i) ≥ L(S) − 2d−qε ≥ L(S) −
The reference to Lemma 3.7 finishes the proof.
10


L(S)
ε
≥
L(S)
1
−
.
2qε
2

Now we speed up Algorithm MBasic. It has two slow parts: deletions from the list SP and checks for
palindromes. Lemmas 3.12 and 3.13 show that, similar to Sect. 3.1, O(1) checks are enough at each iteration.
Lemma 3.12. Suppose that at some iteration the list SP contains consecutive elements I(d), I(c), I(b), I(a).
Then b − a ≤ d − b.
Proof. Let j be the number of the considered iteration. Note that a < b < c < d. Consider the interval
in (10) containing a. If a ∈ (j − 2qε +2 , j], then b − a = 1 and d − b = 2, so the required inequality holds.
Otherwise, let a ∈ (j −2qε +2+x , j −2qε +2+x−1 ]. Then by (9) β(a) ≥ x; moreover, any I(k) such that a < k ≤ j
and β(k) ≥ x is in SP . Hence, b − a ≤ 2x . By Lemma 3.9 each interval, except for the leftmost one, contains
at least 2qε +1 ≥ 4 elements. Thus each of the numbers b, c, d belongs either to the same interval as a or
to the previous interval (j − 2qε +2+x−1 , j − 2qε +2+x−2 ]. Again by (9) we have β(b), β(c), β(d) ≥ x − 1. So
c−b, d−c ≥ 2x−1 , whence the result.
We call an element I(a) of SP valuable at ith iteration if i − a + 1 > answer.len and S[a..i] can be a
palindrome. (That is, Algorithm MBasic does not store enough information to predict that the condition in
its line 7 is false for v = I(a).)
Lemma 3.13. At each iteration, SP contains at most three valuable elements. Moreover, if I(d0 ), I(d) are
consecutive elements of SP and i − d0 < answer.len ≤ i − d, where i is the number of the current iteration,
then the valuable elements are consecutive in SP , starting with I(d).
Proof. Let d be as in the condition of the lemma. If I(d) is followed in SP by at most two elements, we
are done. If it is not the case, let the next three elements be I(c), I(b), and I(a), respectively. If S[a..i]
is a palindrome then S[a+(b−a)..i−(b−a)] is also a palindrome. At the iteration i−(b−a) the tuple I(b)
was in SP , so this palindrome was found. Hence, at the ith iteration the value answer.len is at least
the length of this palindrome, which is i − a + 1 − 2(b − a). By Lemma 3.12, b − a ≤ d − b, implying
answer.len ≥ i − a + 1 − (b − a) − (d − b) = i − d + 1. This inequality contradicts the definition of d;
hence, S[a..i] is not a palindrome. By the same argument, the elements following I(a) in SP do not produce
palindromes as well. Thus, only the elements I(d), I(c), I(b) are valuable.
Now we turn to deletions. The function ttl (x) has the following nice property.
Lemma 3.14. The function x → x + ttl (x) is injective.
Proof. Note that β(x + ttl (x)) = β(x) from the definition of ttl . Hence the equality x + ttl (x) = y + ttl (y)
implies β(x) = β(y), then ttl (x) = ttl (y) by (9), and finally x = y.
Lemma 3.14 implies that at most one element is deleted from SP at each iteration. To perform this
deletion in O(1) time, we need an additional data structure. By BS(x) we denote a linked list of maximal
segments of 1’s in the binary representation of x. For example, the binary representation of x = 12345 and
BS(x) are as follows:
13 12 11 10 9 8 7 6 5 4 3 2 1 0
1 1 0 1 0 0 0 0 1 1 1 0 0 1

BS(12345) = {[0, 0], [3, 5], [10, 10], [12, 13]}

Clearly, BS(x) uses O(log x) space.
Lemma 3.15. Both β(x) and BS(x + 1) can be obtained from BS(x) in O(1) time.
Proof. The first number in BS(x) is β(x). Let us construct BS(x + 1). Let [a, b] be the first segment in
BS(x). If a > 2, then BS(x + 1) = [0, 0] ∪ BS(x). If a = 1, then BS(x + 1) = [0, b] ∪ (BS(x)\[1, b]).
Now let a = 0. If BS(x) = {[0, b]} then BS(x + 1) = {[b+1, b+1]}. Otherwise let the second segment in
BS(x) be [c, d]. If c > b + 2, then BS(x + 1) = [b+1, b+1] ∪ (BS(x)\[0, b]). Finally, if c = b + 2, then
BS(x + 1) = [b+1, d] ∪ (BS(x)\{[0, b], [c, d]}).

11

Thus, if we support one list BS which is equal to BS(i) at the end of the ith iteration, we have β(i). If
I(a) should be deleted from SP at this iteration, then β(a) = β(i) (see Lemma 3.14). The following lemma
is trivial.
Lemma 3.16. If a < b and ttl (a) = ttl (b), then I(a) is deleted from SP before I(b).
By Lemma 3.16, the information about the positions with the same ttl (in other words, with the same
β) are added to and deleted from SP in the same order. Hence it is possible to keep a queue QU (x) of the
pointers to all elements of SP corresponding to the positions j with β(j) = x. These queues constitute the
last ingredient of our real-time Algorithm M.
Algorithm 4 : Algorithm M, ith iteration
1: add I to the beginning of SP
2: if i = 1 then
3:
sp ← f irst(SP )
4: compute BS[i] from BS; BS ← BS[i]; compute β(i) from BS
5: if QU (β(i)) is not empty then
6:
v ← element of SP pointed by f irst(QU (β(i)))
7:
if v = sp then
8:
sp ← next(sp)
9:
delete v; delete f irst(QU (β(i)))
10: add pointer to f irst(SP ) to QU (β(i))
11: read S[i]; compute I(i + 1) from I; I ← I(i + 1)
12: sp ← previous(sp)
13: while i − sp.i + 1 ≤ answer.len and sp 6= last(SP ) do
14:
sp ← next(sp)
15: for all existing v in {sp, next(sp), next(next(sp))} do
16:
if S[v.i..i] is a palindrome and answer.len < i−v.i+1 then
17:
answer ← (v.i, i−v.i+1)

. if exists

Proof of Theorem 3.6. After every iteration, Algorithm M has the same list SP (see Fig. 1) as Algorithm
MBasic, because these algorithms add and delete the same elements. Due to Lemma 3.13, Algorithm M
returns the same answer as Algorithm MBasic. Hence by Proposition 3.11 Algorithm M finds a palindrome
of required length. Further, Algorithm M supports the list BS of size O(log n) and the array QU containing
O(log n) queues of total size equal to the size of SP . Hence, it uses O( log(nε)
) space in total by Lemma 3.10.
ε
The cycle in lines 13–14 performs at most three iterations. Indeed, let z be the value of sp after the previous
iteration. Then this cycle starts with sp = previous(z) (or with sp = z if z is the first element of SP ) and
ends with sp = next(next(z)) at the latest. By Lemma 3.15, both BS(i) and β(i) can be computed in O(1)
time. Therefore, each iteration takes O(1) time.


log n
Remark Since for n−0.99 ≤ ε ≤ 1 the classes O log(1+ε)
and O log(nε)
coincide, Algorithm M uses space
ε
within a log n factor from the lower bound of Theorem 2.7. Furthermore, for an arbitrarily slowly growing
function ϕ Algorithm M uses o(n) space whenever ε = ϕ(n)
n .

3.3

Multiplicative Error for ε > 1

Theorem 3.17. There is a real-time Monte Carlo algorithm solving the problem LPS(S) with multiplicative
log(n) 
error ε = ε(n) ∈ (1, n] using O log(1+ε)
space, where n = |S|.

12

We transform Algorithm M into real-time Algorithm M’ which solves LPS(S) with the multiplicative
log n
error ε > 1 using O log(1+ε)
space. The basic idea of transformation is to replace all binary representations
with those in base proportional to 1 + ε, and thus shrink the size of the lists SP and BS.
First, we assume without loss of generality that ε ≥ 7, as otherwise we can fix ε = 1 and apply Algorithm M. Fix k ≤ 21 (1 + ε) as the largest such even integer (in particular, k ≥ 4). Let β 0 (i) be the position
of the rightmost non-zero digit in the k-ary representation of i. We define
(
0
9
· k β (i) if β 0 (i) > 0,
0
(11)
ttl (i) = 2
4 otherwise.
The list SP 0 is the analog of the list SP from Sect. 3.2. It contains, after ith iteration, the tuples I(j)
for all positions j ≤ i such that j + ttl0 (j) > i. Similar to (10), we partition the range (0; i] into intervals
and then count the elements of SP 0 in these intervals. The intervals are, right to left,




(i − 4, i], i − 92 k, i − 4 , i − 92 k 2 , i − 92 k , . . . , i − 92 k m , i − 92 k m−1 , 0, i − 92 k m .
(12)
For convenience, we enumerate the intervals starting with 0.
Lemma 3.18. Each interval in (12) contains at most 5 elements of SP 0 . Each of the intervals 0, ..., m
contains at least 3 elements of SP 0 .
Proof. The 0th interval contains exactly 4 elements. For any j = 1, . . . , m+1, an element x of the jth
interval is in SP 0 if and only if its position
is divisible by k j ; see (11). The length of this interval is less

9 j
9
than 2 k , giving us upper bound of 2 = 5 elements. Similarly, if j 6= m+1, the jth interval has the length


9 j
9 j−1
and thus contains at least 92 k−1
elements of SP 0 . Since k ≥ 4, the claim follows.
2k − 2k
k
Next we modify Algorithm MBasic, replacing ttl by ttl0 and SP by SP 0 .

log n
Proposition 3.19. Modified Algorithm MBasic finds a palindrome of length `(S) ≥ L(S)
1+ε using O log(1+ε)
space.


Proof. Let S[i..j] be a palindrome of length L(S). Let d = logk L(S)
. Without loss of generality we assume
4
0
d ≥ 0, as otherwise L(S) < 4 ≤ ttl (i) and the palindrome S[i..j] will be detected exactly. Since L(S) ≥ 4k d ,
let a1 < a2 < a3 < a4 < a5 be consecutive positions which are multiples of k d (i.e., β 0 (a1 ), . . . , β 0 (a5 ) ≥ d)
such that a2 ≤ i+j
2 < a3 . Then in particular i < a1 , and there is a palindrome S[a1 ..(i + j − a1 )] such that
a3 ≤ (i + j − a1 ) < a5 . Since a1 + ttl 0 (a1 ) ≥ a5 , this particular palindrome will be detected by the modified
Algorithm MBasic; thus `(S) ≥ a3 − a1 = 2k d . However, we have L(S) < 4k d+1 , hence L(S)
< 2k ≤ (1 + ε).

 log n `(S)
log n
0
.
Space complexity follows from bound on size of the list SP , which is at most 5 log k = O log(1+ε)
To follow the framework from the case of ε ≤ 1, we provide analogous speedup to the checks for palindromes. We adopt the same notion of an element valuable at ith iteration as in Sect. 3.2. First we need the
following property, which is a more general analog of Lemma 3.12; an analog of Lemma 3.13 is then proved
with its help.
Lemma 3.20. Suppose that at some iteration the list SP 0 contains consecutive elements I(d), I(c), and
d ≤ i − answer.len, where i is the number of the current iteration. Further, let I(a) be another element of
SP 0 at this iteration and a < c. If c, d belong to the same interval of (12), then I(a) is not valuable.
Proof. Let c, d belong to the jth interval. Thus they are divisible by k j and d − c = k j . Since a < c, a is
c+a
j
divisible by k j as well. One of the numbers d+a
2 , 2 is divisible by k ; take it as b. Let δ = b − a. If S[a..i]
is a palindrome, then S[b..i − δ] is also a palindrome. Since at the ith iteration the left border of the jth
interval was smaller than c, then at the (i − δ)th iteration this border was smaller than b; hence, I(b) was in
SP 0 at that iteration, and the palindrome S[b..i − δ] was found. Its length is
i − δ − b + 1 = i + 1 + a − 2b ≥ i + 1 + a − (d + a) ≥ i − d + 1 > answer.len,
which is impossible by the definition of answer.len. So S[a..i] is not a palindrome, and the claim follows.
13

Lemma 3.21. At each iteration, SP 0 contains at most three valuable elements. Moreover, if I(d0 ), I(d) are
consecutive elements of SP 0 and i − d0 < answer.len ≤ i − d, where i is the number of the current iteration,
then the valuable elements are consecutive in SP 0 , starting with I(d).
Proof. Let a < b < c < d be such that the elements I(d), I(c), I(b) are consecutive in SP 0 and I(a) belongs to
SP 0 . Then either b, c or c, d are in the same interval of (12), and thus a is not valuable by Lemma 3.20.
To complete the proof, we now turn to deletions, proving the following analog of Lemma 3.14.
Lemma 3.22. The function h(x) = x + ttl 0 (x) maps at most two different values of x to the same value.
Moreover, if h(x) = h(y) and β 0 (x) ≥ β 0 (y), then β 0 (x) = β 0 (h(x)) + 1 and β 0 (y) = 0.
Proof. Let h(x) = h(y). If β 0 (x) = β 0 (y) then ttl0 (x) = ttl0 (y) by (11), implying x = y. Hence all preimages
0
of h(x) have different values of β 0 . Assume β 0 (x) > β 0 (y). Then we have, for some integer j, x = j · k β (x)
0
0
and h(x) = (j + 4)k β (x) + k2 · k β (x)−1 by (11). Since k is even, we get β 0 (h(x)) = β 0 (x) − 1. If β 0 (y) > 0,
we repeat the same argument and obtain β 0 (x) = β 0 (y), contradicting our assumption. Thus β 0 (y) = 0. The
claim now follows.
We also define a list BS 0 (x),
encoding of the k-ary representation of x. The
 which maintains an RLE
n
0
list BS 0 (x) has length O log
,
can
be
updated
to
BS
(x+1)
in O(1) time, and provides the value β 0 (x)
log k
in O(1) time also (cf. Lemma 3.15). Further, Lemma 3.16 holds for the function ttl0 , so we introduce the
queues QU 0 (x) in the same way as the queues QU (x) in Sect. 3.2. Having all the ingredients, we present
Algorithm M’ which speeds up the modified Algorithm MBasic and thus proves Theorem 3.17. The only
significant difference between Algorithm M and Algorithm M’ is in the deletion of tuples from the list
(compare lines 5–9 of Algorithm M against lines 5–15 of Algorithm M’).
Algorithm 5 : Algorithm M’, ith iteration
1: add I to the beginning of SP 0
2: if i = 1 then
3:
sp ← f irst(SP 0 )
4: compute BS 0 [i] from BS 0 ; BS 0 ← BS 0 [i]; compute β(i) from BS 0
5: if QU 0 (β(i) + 1) is not empty then
6:
v ← element of SP 0 pointed by f irst(QU 0 (β(i)))
7:
if v.i + ttl0 (v.i) = i then
8:
if v = sp then
9:
sp ← next(sp)
10:
delete v; delete f irst(QU 0 (β(i) + 1))
11: v ← element of SP 0 pointed by f irst(QU 0 (0))
12: if v.i + ttl0 (v.i) = i then
13:
if v = sp then
14:
sp ← next(sp)
15:
delete v; delete f irst(QU 0 (0))
16: add pointer to f irst(SP 0 ) to QU 0 (β(i))
17: read S[i]; compute I(i + 1) from I; I ← I(i + 1)
18: sp ← previous(sp)
19: while i − sp.i + 1 ≤ answer.len and sp 6= last(SP 0 ) do
20:
sp ← next(sp)
21: for all existing v in {sp, next(sp), next(next(sp))} do
22:
if S[v.i..i] is a palindrome and answer.len < i−v.i+1 then
23:
answer ← (v.i, i−v.i+1)

14

. if exists

3.4

The Case of Short Palindromes

A typical string contains only short palindromes, as Lemma 3.23 below shows (for more on palindromes in
random strings, see [16]). Knowing this, it is quite useful to have a deterministic real-time algorithm which
finds a longest palindrome exactly if it is “short”, otherwise reporting that it is “long”. The aim of this section
is to describe such an algorithm (Theorem 3.24).
Lemma 3.23. If an input stream S ∈ Σ∗ is picked up uniformly at random among all strings of length n,
where n ≥ |Σ|, then for any positive constant c the probability that S contains a palindrome of length greater
log n
is O(n−c ).
than 2(c+1)
log |Σ|
Proof. A string S contains a palindrome of length greater than m if and only if S contains a palindrome of
length m+1 or m+2. The probability P of containing such a palindrome is less than the expected number
M of palindromes of length m+1 and m+2 in S. A factor of S of length l is a palindrome with probability
1/|Σ|bl/2c ; by linearity of expectation, we have
M=
Substituting m =

2(c+1) log n
,
log |Σ|

n−m−1
n−m
+
.
b(m+1)/2c
|Σ|
|Σ|b(m+2)/2c

we get M = O(n−c ), as required.

Theorem 3.24. Let m be a positive integer. There exists a deterministic real-time algorithm working in
O(m) space, which
- solves LPS(S) exactly if L(S) < m;
- finds a palindrome of length m or m+1 as an approximated solution to LPS(S) if L(S) ≥ m.
Proof. To prove Theorem 3.24, we present an algorithm based on the Manacher algorithm [14]. We add two
features: work with a sliding window instead of the whole string to satisfy the space requirements and lazy
computation to achieve real time. (The fact that the original Manacher algorithm admits a real-time version
was shown by Galil [7]; we adjusted Galil’s approach to solve LPS.) The details follow.
j−i
We say that a palindromic factor S[i..j] has center i+j
2 and radius 2 . Thus, odd-length (even-length)
palindromes have integer (resp., half integer) centers and radiuses. This looks a bit weird, but allows one to
avoid separate processing of these two types of palindromes. Manacher’s algorithm computes, in an online
fashion, an array of maximal radiuses of palindromes centered at every position of the input string S. A
variation, which outputs the length L of the longest palindrome in a string S, is presented as Algorithm
EBasic below. This variation is similar to the one of [13]. Here, n stays for the length of the input processed
so far, c is the center of the longest suffix-palindrome of the processed string. The array of radiuses Rad has
length 2n−1 and its elements are indexed by all integers and half integers from the interval [1, n]. Initially,
Rad is filled with zeroes. The left endmarker is added to the string for convenience. After each iteration, the
following invariant holds: the element Rad[i] has got its true value if i < c and equals zero if i > c; the value
Rad[c] = n − c can increase at the next iteration. Note that the longest palindrome in S coincides with the
longest suffix-palindrome of S[1..i] for some i. At the moment when the input stream ends, the algorithm
has already found all such suffix-palindromes, so it can stop without filling the rest of the array Rad.
Note that n calls to AddLetter perform at most 3n iterations of the cycle in lines 10–15 (each call performs
the first iteration plus zero or more “additional” iterations; the value of c gets increased before each additional
iteration and never decreases). So, Algorithm EBasic works in O(n) time but not in real time; for example,
reading the last letter of the string an b requires n iterations of the cycle.
By conditions of the theorem, we are not interested in palindromes of length > m+1. Thus, processing
a suffix-palindrome of length m or m+1 we assume that the symbol comparison in line 12 fails. So the
procedure AddLetter needs no access to S[i] or Rad[i] whenever i < n − m. Hence we store only recent
values of S and Rad and use circular arrays CS and CRad of size O(m) for this purpose. For example,
the symbol S[n−i] is stored in CS[(n−i) mod (m+1)] during m+1 successful iterations of the outer cycle
(lines 3–6), and then is replaced by S[n−i+m+1]; the same scheme applies to the array Rad. In this way,
all elements of S and Rad, needed by Algorithm EBasic, are accessible in constant time. Further, we define
15

Algorithm 6 : Algorithm EBasic, ith iteration
1: procedure Manacher
2:
c ← 1; L ← 1; n ← 1; S[0] ←’#’
3:
while not (end of input) do
4:
read(S[n + 1]); AddLetter(S[n + 1])
5:
if 2 ∗ Rad[c] + 1 > L then
6:
L ← 2 ∗ Rad[c] + 1
7:
return L
8: procedure AddLetter(a)
9:
s←c
10:
while c < n + 1 do
11:
Rad[c] ← min(Rad[2 ∗ s − c], n − c)
12:
if c + Rad[c] = n and S[c − Rad[c] − 1] = a then
13:
Rad[c] ← Rad[c] + 1
14:
break
15:
c ← c + 0.5
16:
n←n+1

. longest suf-pal of S[1..n + 1] is found
. next candidate for the center

a queue Q of size q for lazy computations; it contains symbols that are read from the input and await
processing.
Now we describe real-time Algorithm E. It reads input symbols to Q and stops when the end of the input
is reached. After reading a symbol, it runs procedure Manacher, requiring the latter to pause after three
“inner iterations” (of the cycle in lines 10–15). The procedure reads symbols from Q; if it tries to read from
the empty queue, it pauses. When the procedure is called next time, it resumes from the moment it was
stopped. Algorithm E returns the value of L after the last call to procedure Manacher.
To analyze Algorithm E, consider the value X = q + n − c after some iteration (clearly, this iteration has
number q+n) and look at the evolution of X over time. Let ∆f denote the variation of the quantity f at
one iteration. Note that ∆(q+n) = 1. Let us describe ∆X. First assume that the iteration contains three
inner iterations. Then ∆n = 0, 1, 2 or 3 and, respectively, ∆c = 1.5, 1, 0.5 or 0. Hence
∆X = 1 − ∆c = 1 + (∆n − 3)/2 = 1 − (1 − ∆q − 3)/2 = −(∆q)/2.
If the number of inner iterations is one or two, then q becomes zero (and was 0 or 1 before this iteration);
hence ∆n = 1 − ∆q ≥ 1. Then ∆c ≤ 0.5 and finally ∆X > 0. From these conditions on ∆X it follows that
(∗) if the current value of q is positive, then the current value of X is less than the value of X at the
moment when q was zero for the last time.
Let X 0 be the previous value of X mentioned in (∗). Since the difference n − c does not exceed the radius of
some palindrome, X 0 ≤ m/2. Since q ≤ X < X 0 , the queue Q uses O(m) space. Therefore the same space
bound applies to Algorithm E.
It remains to prove that Algorithm E returns the same number L as Algorithm EBasic with a sliding
window, in spite of the fact that Algorithm E stops earlier (the content of Q remains unprocessed by procedure
Manacher). Suppose that Algorithm E stops with q > 0 after n iterations. Then the longest palindrome
that could be found by processing the symbols in Q has the radius X = n + q − c. Now consider the iteration
mentioned in (∗) and let n0 and c0 be the values of n and c after it; so X 0 = n0 −c0 . Since q was zero after that
iteration, procedure Manacher read the symbol S[n0 ] during it; hence, it tried to extend a suffix-palindrome
of S[1..n0 −1] with the center c00 ≤ c0 . If this extension was successful, then a palindrome of radius at least
X 0 was found. If it was unsuccessful, then c0 ≥ c00 + 1/2 and hence S[1..n0 −1] has a suffix-palindrome of
length at least X 0 − 1/2. Thus, a palindrome of length X ≤ X 0 − 1/2 is not longer than a longest palindrome
seen before, and processing the queue cannot change the value of L. Thus, Algorithm E is correct.

16

The center and the radius of the longest palindrome in S can be updated each time the inequality in line
6 of procedure Manacher holds. Theorem 3.24 is proved.
Remark Lemma 3.23 and Theorem 3.24 show a practical way to solve LPS. Algorithm E is fast and
lightweight (2m machine words for the array Rad, m symbols in the sliding window and at most m symbols
in the queue; compare to 17 machine words per one tuple I(i) in the Monte Carlo algorithms). So it makes
direct sense to run Algorithm M and Algorithm E, both in O(log n) space, in parallel. Then either Algorithm
E will give an exact answer (which happens with high probability if the input stream is a “typical” string) or
both algorithms will produce approximations: one of fixed length and one with an approximation guarantee
(modulo the hash collision).

References
[1] A. Apostolico, D. Breslauer, and Z. Galil. Parallel detection of all palindromes in a string. Theoret.
Comput. Sci., 141:163–173, 1995.
[2] P. Berenbrink, F. Ergün, F. Mallmann-Trenn, and E. Sadeqi Azer. Palindrome recognition in the streaming model. In STACS 2014, volume 25 of LIPIcs, pages 149–161, Germany, 2014. Schloss DagstuhlLeibniz-Zentrum fuer Informatik, Dagstuhl Publishing.
[3] D. Breslauer and Z. Galil. Real-time streaming string-matching. In Combinatorial Pattern Matching,
volume 6661 of LNCS, pages 162–172, Berlin, 2011. Springer.
[4] R. Clifford, A. Fontaine, E. Porat, B. Sach, and T. A. Starikovskaya. Dictionary matching in a stream.
In ESA 2015, volume 9294 of LNCS, pages 361–372. Springer, 2015.
[5] R. Clifford, A. Fontaine, E. Porat, B. Sach, and T. A. Starikovskaya. The k -mismatch problem revisited.
In SODA 2016, pages 2039–2052. SIAM, 2016.
[6] F. Ergün, H. Jowhari, and M. Saglam. Periodicity in streams. In RANDOM 2010, volume 6302 of
LNCS, pages 545–559. Springer, 2010.
[7] Z. Galil. Real-time algorithms for string-matching and palindrome recognition. In Proc. 8th annual
ACM symposium on Theory of computing (STOC’76), pages 161–173, New York, USA, 1976. ACM.
[8] Z. Galil and J. Seiferas. A linear-time on-line recognition algorithm for “Palstar”. J. ACM, 25:102–111,
1978.
[9] P. Gawrychowski, F. Manea, and D. Nowotka. Testing generalised freeness of words. In STACS 2014,
volume 25 of LIPIcs, pages 337–349. Dagstuhl Publishing, 2014.
[10] M. Jalsenius, B. Porat, and B. Sach. Parameterized matching in the streaming model. In STACS 2013,
volume 20 of LIPIcs, pages 400–411. Dagstuhl Publishing, 2013.
[11] R. Karp and M. Rabin. Efficient randomized pattern matching algorithms. IBM Journal of Research
and Development, 31:249–260, 1987.
[12] D. E. Knuth, J. Morris, and V. Pratt. Fast pattern matching in strings. SIAM J. Comput., 6:323–350,
1977.
[13] D. Kosolobov, M. Rubinchik, and A. M. Shur. Finding distinct subpalindromes online. In Proc. Prague
Stringology Conference. PSC 2013, pages 63–69. Czech Technical University in Prague, 2013.
[14] G. Manacher. A new linear-time on-line algorithm finding the smallest initial palindrome of a string.
J. ACM, 22(3):346–351, 1975.

17

[15] B. Porat and E. Porat. Exact and approximate pattern matching in the streaming model. In FOCS
2009, pages 315–323. IEEE Computer Society, 2009.
[16] M. Rubinchik and A. M. Shur. The number of distinct subpalindromes in random words. Fundamenta
Informaticae, 145:371–384, 2016.
[17] A. C.-C. Yao. Probabilistic computations: Toward a unified measure of complexity (extended abstract).
In FOCS 1977, pages 222–227. IEEE Computer Society, 1977.

18

