<p>I had a use for palindromes as follows:</p>

<p>A string of length <span class="math-container">$n$</span> and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal.</p>

<p>Now after identifying you may ask how many equivalence classes have certain properties. And then the number of equivalence classes is directly related to the number of palindromes. If there  are <span class="math-container">$p_n$</span> palindromes then there are
<span class="math-container">$$p_n+(2^n-p_n)/2$$</span>
equivalence classes of binary strings. </p>

CC BY-SA 4.0
2020-02-21T05:00:52.357Z
2020-02-21T05:00:52.357Z
Bjørn Kjos-Hanssen
<p>I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas. </p>

<p>I'm unsure as to whether this is because the question is purely <em>theoretically interesting</em> (in terms of finding good lower bounds), or there are <em>practical use cases</em> for this (in terms of genetics, or even other use cases I don't know of).</p>

<p>So, what do studying palindromes offer us? Do they offer theoretical insight into other string problems --- the way matrix multiplication and matrix inversion offer insights into each other? Are they practically useful? Or is it "just fun"?</p>

<ds.algorithms><string-matching>
Are string palindrome questions practically interesting?
Siddharth Bhat
# Are string palindrome questions practically interesting?

(Asked by: username_0 on 2020-02-20)

I've been reading Don Gusfield's "Algorithms on Strings, Trees, and Sequences", and quite a some chunk of the textbook concentrates on palindromic-related ideas.

I'm unsure as to whether this is because the question is purely *theoretically interesting* (in terms of finding good lower bounds), or there are *practical use cases* for this (in terms of genetics, or even other use cases I don't know of).

So, what do studying palindromes offer us? Do they offer theoretical insight into other string problems --- the way matrix multiplication and matrix inversion offer insights into each other? Are they practically useful? Or is it "just fun"?

**Tags:** ds.algorithms, string-matching

---

## 1 answers

### Answer by username_1 on 2020-02-21. Score: 2 | Accepted answer

I had a use for palindromes as follows:

A string of length $n$ and its reversal have the same complexity. Thus, when studying complexity of strings you can identify a string with its reversal.

Now after identifying you may ask how many equivalence classes have certain properties. And then the number of equivalence classes is directly related to the number of palindromes. If there are $p\_n$ palindromes then there are
$$p\_n+(2^n-p\_n)/2$$
equivalence classes of binary strings.


---

